What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
Authors: Omar Bennouna
Amine Bennouna
Saurabh Amin
Asuman E. Ozdaglar
Venue: NeurIPS 2025 poster ()
Keywords: data informativeness
linear optimization
Blackwell's informativeness theory
data value
data-driven decision-making
Primary area: theory

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.

What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
Omar Bennouna
Amine Bennouna
Saurabh Amin MIT amins@mit edu
MIT
Northwestern University amine. www..emwmomootottttette..mmmmmm. edu
omarben@mit.co edu
Asuman Ozdaglar MIT asumanSmit.cm edu
Abstract
We study the fundamental question of how informative a dataset is for solving given decision-making task. In setting, the dataset provides partial infor- mation about unknown parameters that influence task outcomes. Focusing on linear programs, characterize when dataset is sufficient to recover 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 minimal least-costly sufficient dataset. Our results reveal that small, well-chosen datasets can often fully determine optimal decisions offeerins-oferrinn a principled foundation for task-aware data selection.
Introduction
Decision-making problems are often performed under incomplete knowledge of the state of nature- that is, they rely parameters that must be learned estimated. In practice, experts draw combination of domain knowledge and experience from previously solved tasks. With the recent surge in data availability, data-driven decision-makinn has become dominant paradigm: data now plays a central role in complementing contextual knowledge to guide decisions. This paper seeks to understand the informational value of given dataset with respect to specific decision decision-making making task. More precisely, we ask: to what extent does a dataset enable recovery of the optimal decision, given task structure and prior knowledge?
The fundamental question of data informativeness or its value has several important implications. recision-making task, which data
One key implication is data collection: when faced with should be collected to effectively generalize prior knowledge to the new setting? Ideally, one seeks the smallest-op least costly-yet yet most informative dataset. A second major implication lies in computing. Recent successes large-scale models (e.g., LLMs) have been driven by large-scale data and advances in computing. However, computing cost remains a significant bottleneck. Identifying the most informative subset of data for a specific task can significantly reduce dataset size and, consequently, training costs. Quantifying data value also impacts mechanism design in data markets and considerations around privacy.
A general setting for studying this question is follows. Suppose the meeiiissmmmakr's goal is to select a decision æ E minimizing a loss L(x, 0)) which depends on an unknown parameter-staie of nature- 0 E θ. A dataset D {gi..... gN consists of points at which the loss is evaluated: it
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

provides observations {L( 0) + c(q1. ()......(.o,,, 0) + c(gN, 8)} partially informing on the true state of nature 8, where the random variable e(.,-) models noisy observations. The Dpcision-maker can then use the observations along with their prior knowledge (set restriction 0 E @) to select decision x E X' minimizing [xx 0). The central question is: which datasets 'D allow to recover the task-optimal decision, given the prior knowledge encoded in the uncertainty set @ In the rest of the paper, we study this question in the setting of linear programming- with linear loss L and polyhedral decision set wher the task structure enables a sharp analysis.
To illustrate this formalism with an example, consider hiring problem in which decision-maker is given a list of candidates and their resumes and decides which subset of candidates to interview in order to reveal their value, and ultimately make a hiring decision. This problem has been studied in various settings (Purohit et al. 2019 [Epstein and Ma 2024), including within the popular Secretary Problem (Kleinberg 2005| Arlotto and Gurvich 2019, Bray 2019). Prior work typically assumes a sequential, adaptive model, where interviews and hiring decisions occur in an online fashion. However, in many real-world scenarios
as hiring PhD students or faculty- -te set of candidates to interview must be chosen in advance, with hiring decisions made afterward based on all interview outcomes. This latter offline setting is a natural instance of the data informativeness problem.
Formally, hiring from d candidates is a decision-making problem where a decision consists of a binary vector x E X C {0, indicating which candidates hire. The feasible set X encodes organizational constraints, such as a maximum number of hires Σi= 2; S k, or maximum expertise- based quotas Eier, Iz k; for subsets 15 C [d], to name a few. Each candidate has an unknown value 0g. with 0 E θ C Rd modeling prior information on these values. It consists here in (i) candidates' resumes, which can be seen as features Φ = -011...,00 Qa) E R and (ii) historical hiring data, which is pairs of resumes and observed value (δ1. .1)....
8n)) Specifically, θ = {0 E RC 3a E R², Je, E E3 s.t. 0 = a Φ + e, 0 = a ② + e'} with & C E c R' noise sets. The loss incurred by a decision r under values θ is L(x, 0) = - x x-ehe negative total value 0
of selected candidates. A dataset D {q E 1) Ee qi 1} is subset of candidates to interview, and each interview q E D. qj 1, reveals a, possibly noisy, evaluation of a given candidate j's value L(g, 0) 0g which complements the prior information embedded in +. The goal in this application is to select the smallest subset of candidates to interview (dataset) to recover the optimal hiring decision: that is, the smallest, informative dataset for the given task.
d
The question of data informativeness is related to several extensively studied topics in economics, statistics, computer science, and operations research literature. Below, we highlight a few of these areas and the angle with which they approached this question.
Active Learning, Bandits and Adaptive Experimental Design. In many data-driven settings. informativeness approached via adaptive, sequential data collection. Active learning (Settles) 2009 Zheng et al. 2017) seeks to sequentially select data points that improve a classifier by minimizing predictive loss, while bandit algorithms (Lattimore and Szepesvári 2020 Carlsson et al. 2024) aim to optimize decisions through sequential exploration. Adaptive experimental design (Zhao 2024) similarly selects experiments to maximize information gain about unknown parameters, often guided by Bayesian criteria such as posterior variance reduction. These approaches rely real-time feedback to guide data acquisition and typically analyze asymptotic behavior. However, in practical applications- such surveys or field trials queries must often be selected in advance, and outcomes are revealed only afterward. In such settings, adaptivity is infeasible.
In contrast to these paradigms, we study fixed datasets in a non-adaptive, finite-sample regime, focusing on geometric conditions for optimal decision recovery rather than statistical estimation error. We show that, even without adaptivity, one can precisely characterize which datasets are sufficient to recover task-optimal
-ffferinn an offline analogue to adaptive data selection.
Blackwell's Informativeness Theory. One of the carliest and most celebrated frameworks for comparing datasets Blackwell's 's theory of informativeness (Blackwel]1953) In this framework. a dataset is abstracted as an experiment, which generates a signal E S drawn from a distribution P(s(0), informing on E e, the unknown state of nature. This equivalent to our framing above, with the signal being s (I(q,, 0) + c(11, f). ... L(gx. 0) + c(qN, f)) and the noise terms specifying the conditional distribution. Two datasets (experiments) are compared by whether one enables better decision-making across all loss functions and priors. Formally, an experiment P is
2

---

more informative than experiment Q if
for all loss L and prior x inf Fa Q0 ((x)) ((((s)))) inf [E (e (1)0))))))) 8:S-4X 8:S-+X
Blackwell's seminal result shows that this criterion is equivalent to several elegant characterizations, notably through the notion of garbling (de Oliveira 2018).
Blackwell's 's informativeness criterion imposes a strict requirement: it compares datasets by whether they enable better decisions across all possible tasks. In contrast, our work fixes the decision task (loss function I. and structure 2') and asks which datasets suffice to recover the task-optimal decision. This restriction aligns better with practical applications but also makes the informativeness question more delicate: as Le Cam (1996) observed, such questions may become "complex or impossible depending on the statistician's 's goal". Whereas Blackwell compares datasets by their universal utility, our work develops a tractable, task-specific notion of informativeness grounded in the structure of the decision task itself.
Influence Functions and Robust Statistics. Influence functions, originating in robust statistics (Huber 1992. Hampel et al. 1986), quantify the local impact of individual data points estimators and have recently received renewed interest (Broderick et al. 2023). Similar approaches include DataShapely (Ghorbani and Zou 2019 K Kwon and Zou 2022 Jiang et al. 2023 Tia al. 2023). and Datamodels (Ilyas et al. [022] Dass et al. 2025 Ilas and Engstrom 2025). These methods typically analyze how small perturbations to a dataset affect the output of a fixed estimator. However, key limitation of this approach is that data value is generally "non-additive": the informativeness of an individual data point is not intrinsic, but rather related to the data set as whole. Our focus is on the joint informativeness of the full cattaset-characterriiing when a collection of observations, as whole, suffices to recover the task-optimal decision. Joint informativeness, combinatorial in nature, is a more challenging problem (Rubinstein and Hopkins 2024, FFrennd and Hopkins 2023). Furthermore, while influence functions assess sensitivity in estimation problems under fixed inference procedures. our framework evaluates data informativeness with respect to a decision task, at a dataset-level independently of any specific inference or optimization procedure.
Data informativeness is a fundamental problem that relates to multiple literature streams such as Stochastic Probing (Weitzman 1979, Singla 2018 Gallego and Segev 2022), Optimal Experimental Design (Chaloner and Verdinelli 1995 Singh and Xie 2020) and Algorithms with Predictions
Mitzenmaccher and Vassilvitskii 2020 but detailed comparison is beyond the scope of this paper.
Contributions. This paper addresses the problem of evaluating the informativeness of datasets relative specific decision-making task. We study informativeness in the sense of being able to recover the task's 's optimal solution. This problem is challenging: it is combinatorial in nature, requiring assessment of the value of different combinations of data points. Moreover, informativeness in decision -eriiiin-mmainggaaa is difficult to quantify. One must identify how information in dataset is relevant to decisions in the feasible set X, relative to prior information encoded in the uncertainty set O.
To be able to derive precise insights, we focus on tasks that can be formulated as linear programs-a broad and expressive class of decision-makinn problems whose geometric structure enables precise theoretical analysis. Our main contributions are as follows:
Geometric Characterization of Dataset Sufficiency: We prove a necessary and sufficient condition (Theorem T) under which dataset is sufficiett to recover the optimal decision for a linear program under cost uncertainty. This condition is framed geometrically: a dataset is sufficient if it spans the task-relevant directions that govern what can change the optimal solution, given the structure of the feasible set X' and the uncertainty set O.
We show that the span of relevant directions for dataset sufficiency can equivalently be expressed as the span of differences between optimal solutions under different cost vectors in the uncertainty set. This characterization (Theorem 2 provides an algorithmically accessible formulation for evaluating and constructing sufficient datasets.
Constructive Characterization via Reachable Optimal Solutions:
Building on these characterizations, we develop an iterative algorithm that constructs a minimal sufficient dataset. When the uncertainty set is polyhedral, the algorithm terminates number of steps equal the size of the minimal sufficient dataset, and each step involves solving a tractable mixed-integer program.
Efficient Data Collection Algorithm:
3

---

2 Further literature review
Parametric Programming and Sensitivity Analysis. This stream of work aims to understand how the optimal decision and value change when the underlying problem parameters are perturbed. Sensitivity analysis typically focuses on small, local perturbations, asking how far one can move in given direction while preserving optimality (Ward and Wendell (1990), Xu and Burer (2017)). Multiparametric programming. by contrast, considers larger, structured changes in the parameters and aims to characterize the full mapping from parameters to optimal solutions, often by partitioning the parameter space into regions where the set of minimizers remains constant (Gal and Nedoma (1972), |Saaty and Gass [1954). The connection to our work lies in the shared goal of studying the interplay between problem parameters and optimal solutions. However, while sensitivity analysis and parametric programming aim to describe how solutions evolve parameters vary, our focus is on identifying which datasets- i.c. which function parameters are sufficient to recover the optimal solution.
Contextual Optimization. In contextual optimization, in our setting, pocision-maker aims to choose decision x & X' minimizing the loss L(x, 0), where 0 is unknown (Sadana et al. 2023 Hu et al. 2022 Bertsimas and Kallus 2020). The decision maker also has access to side information & E RR that is correlated with 0. Given empirical samples from the joint distribution of Φ and 0, needs to learn policy æ that maps side information 6 to an optimal decision x E X. Within this literature, much of the work-particularty in linear optimization- foruuuss on constructing data-driven surrogates of the unknown loss function, with the goal of improving decision quality rather than merely predicting losses. A prominent line of research in this direction is the predict-andoppingg framework (Elmachtoub and Grigas 2022). This paradigm is similar to ours in the sense that the aim is to directly focus on optimal decisions rather than predictions. However, the fundamental difference between contextual optimization and our setting is that our main concern is to understand how to select the most informative dataset, whereas in contextual optimization, the data already given and one must determine how to use it to produce an optimal decision policy. More recent work in contextual optimization has also considered adaptive data-selection strategies (Liu ct al. 2023).
the
Set-based vs. Distribution-based Modeling of Uncertainty, In our problem, we chose to model uncertainty through a set (0 E +) similar to the robust optimization literature. This is in contrast to modeling uncertainty as 9 following some known distribution, as in Bayesian optimization, for example. This modeling choice of uncertainty has been widely discussed in the robust optimization literature (Ben-Tal et al. 2009 Bertsimas et al. 2011 Delage and Ye 2010).
Set-based uncertainty has several practical advantages in our context compared to distribution- uncertainty. For instance, set-based approaches typically rely on milder and often more realistic assumptions, as they do not require fully specified probabilistic model of uncertainty. Instead, uncertainty is captured through bounds or confidence sets that are valid for a general class of distributions (such as with given finite moments, in settings where the true distribution is unknown, partially observed, or difficult to estimate reliably. Moreover, set- set-based formulations often lead to more tractable optimization problems and less sensitive to model misspecification (see Bertsimas et al. (2018). Ben- Tal and Nemirovski (2002)). For instance, in Bayesian Experimental Design, standard approaches require expensive computations to evaluate expected information gains in high-dimensional spaces and are highly sensitive to model misspecification, which can lead to suboptimal results (Rainforth et al. 2024
given support). This is particularly appealing
3 Problem Formulation
We study decision-making tasks modeled as linear programs (LPs). That where the loss L(x, 0) = @T is linear, and the decision set X' {2 E Rd, Ar b, 2 0} is a polyhedron, for A Rmxd b E Rm. The decision-maker's task is then solve the LP
min c x, zEX
(1)

---

where A' is assumed to be bounded. The unknown parameter or state of nature -here is the cost vector The decision-makee only knows it be in some given uncertainty set C C R which captures prior information e (these are 0 and ().
To solve the linear program, the decision-maker the task. A dataset D с Rd consists of a set of queries to evaluate the objective function. That is dataset gives access the observations c q for q D. We focus on the noiseless setting, where each observation c' is exact. This simplification enables a sharp characterization of informativeness. We then show how the core insights naturally extend to noisy observations in Proposition B
complement their knowledge C by data
The fundamental question we seek to address which datasets are sufficient to solve the linear program. We formalize such property next. Here ((X) denotes subsets of X.
Definition 1 (Sufficient Decision Dataset). A set D (qi..... .NN is sufficient decision dataset for uncertainty set C and decision set X' if there exists mapping X RN - P(X') such that
VC C, A (c q1....,,'' c. 9N)
arg min c zEA
When there is ambiguity on C and X, simply say that D is sufficient decision dataset.
Definition I states that dataset is sufficient if there exists a mapping that can recover the optimal solution the recision-making task using only the dataset's observations and prior information (c E C).
Naturally, D ea), where (e))se(d) canonical basis vectors is sufficient decision dataset. In fact, observing cTc, c for all E [d] amounts to fully observing c, and solving the linear program with complete information with ((c" Q)EE) = (c) == arg min T x. The question is then whether there exist other, potentially smaller sufficient datasets. That is, what is the least amount of information required to solve the task? As we will show, whether a dataset is sufficient depends critically the uncertainty set C and the feasible region X, since these jointly determine which directions of c affect the optimal decision.
If the goal is to solve the linear program [ natural relaxation of Definition | is require only that a dataset permits recovery of some optimal solution, rather than the entire sel of optimal solutions. We show in the next proposition that, under mild structural assumptions, this property is equivalent to the property of Definition] [[] This means that any dataset that recovers one solution also recovers all solutions. The proof of this equivalence is nontrivial and relies several structural results develop later in the paper.
Proposition (One vs All Optimal Solutions). Let be an open convex set and D = {91 ........9N AN3 dataset. The following equivalent:
1. There exists mapping X RR - P(X) such that Vc C, X (c n,...,, cT...,,TN])) arg min cTz.
2. There exists mapping RN X such that Ve e C, & (cT qu...., c cTqN) arg min cTz. z.
Notice that observing cT for all q ' is equivalent to observing the projection of onto the span D. This implies that Definition equivalent to the following characterization, which gives a valuable perspective. For any subspace F c Rd and E Rd, we denote uF the projection of in F.
Proposition 2. D = (gn......N) } is sufficient decision dataset for uncertainty set C and decision set X if and only if
Ve,d E EC, Cspan D Cspan D arg min e arg min c x. ZEX
xEX
In words, Proposition 2 formulates that dataset D is sufficient if any two cost vectors that equivalent from the perspective of the information provided by D (and C) lead to the same optimal solutions in the decision-mate making problem.
This characterization suggests a natural algorithm for solving the LP IT when given sufficient
datasct D {gi...., gg.) Suppose observe values o, c q i E [] for unknown cost
5

---

vector E C. We then compute è E arg min (E the decision problem min è x. This procedure recovers the projection of onto span 'D while respecting the prior of C. This ensures Espan D Cspan D as c E C, and since the dataset sufficient, guarantees that the resulting decision is task-optimal (Proposition 2
(c' (c
E' C) and use è to solve
When the observations are noisy, a sufficient dataset can still yield a correct decision. In particular, estimating an approximate cost vector è via least-squares from noisy observations still leads to an optimal decision, long as the noise is sufficiently small.
(Noisy Observations). Let C Rd be an open set, and D == (q1....; ., 4r) a sufficient decision dataset for C. Let c E C. Let Els..r, R, and for all [r], o, q + Es. Let è arg min ( {_ im (c' q: 0,)2 : d' C). There exists such that if ||ell < K, then arg min ē arg minzex x.
Proposition
4 Characterizing Sufficient Datasets
Given uncertainty set C and decision set X, would like characterize sufficient decision datasets and eventually construct such datasets. As in Blackwell's theory, the difficulty of such characterizations depends the richness of the uncertainty set C. In fact, the first results by Blackwell (1949] 1951) and [Sherman (1951) were for set C with only two elements. That is, the data needs to distinguish only two alternative states of nature. The result later extended to the finite sets by Blackwell (1953) and then to infinite sets with regularity conditions by Boll (9555..
4.1 Characterization Under No Prior Knowledge
We begin with the case of no prior knowledge, i.e., Rd, which isolates how the structure of the decision set X' alone determines what information is necessary to recover the optimal solution. We will then study the case of convex sets. To formulate our result, define Fg = span {ez, E [d], 3r X, Ii * 0} where is the i-th element of the canonical basis. Fo captures the coordinates that can take non-zero values in feasible solutions of X. That is Fo captures coordinates that are identically zero in all feasible solutions: 6₁ E Fot = Vx E X, Fz =.
Proposition 4. Suppose C Rd. 'D is sufficient decision dataset if and only if FonKer A C span D. Furthermore, when the condition Fo f Ker C span D is not satisfied, for any mapping & IR X, and any K > 0, there exists E Rdd such that c. i (c qq....,c" qN) 2 K + minnex c c.....,Tqqx)
Proposition D iidicates that, already with no prior knowledge, not all the information on c required to solve the optimization problem. In fact, the dataset needs only to capture "relevant" information for the decision-making task, defined by X. The proposition shows that these are the directions in the null space of A (Ker A), that act on active variables (F)).
Let us provide an intuitive explanation for this result. Since every x E X satisfies = 0 for all e, E Fot,, the components of c along Fot do not influence the objective and the dataset D need not capture these directions. Hence, we can, without loss of generality, restrict attention to the subspace Fo and replace the variable æ with its projection F.. The objective function can be decomposed as
Ker T '(Ker A)1 S. Because X' lies in affine space parallel to Ker A, any change from a feasible decision x to another feasible decision x + necessarily verifies d E Ker A. Therefore, ([ker A)" is constant across all feasible solutions. This means that only the projection of i Ker A matters when comparing costs of feasible decisions.
The second part of Proposition 4 formalizes a dichotomy: either the dataset is sufficient and enables optimal decision recovery, any algorithm may incur arbitrarily large suboptimality in the worst case. This sharp divide, however, is specific to the unstructured case = Rd. As we will see next, imposing structure on C significantly enriches the notion of sufficiency.
4.2
Characterization under Convex Uncertainty Sets
The goal now is to characterize sufficient datasets for any convex uncertainty set C. We start by introducing some geometric notions that are useful to understand the sufficiency of dataset.

---

Definition 2 (Extreme Points). An element E A' is an extreme point if and only if there are no À E (0, 1) and y, 2 E such that = Ay 11-A)22 The set of extreme points of X' is denoted X
From every extreme point, there is a set of feasible directions that allow changing the solution while remaining in the polyhedron X'ethe feasible region. Out of these feasible directions, extreme directions allow moving to "neighboring" extreme points.
Proposition 5 (Feasible and Extreme Directions). For every x² X',, denote
FD(x*) = {6 R E 0, x²+ + E
the set of feasible directions from X. FD(x") is polyhedral cone and FD F F Ker A. We denote ( ) the set of extreme directions of FD(x"): non-zero vectors in (D("") that cannor be written a convex combination of two non-proportional elements of FD(x*).
In linear programs, optimal solutions are attained in extreme points X Every extreme point is associated with a set of cost vectors e for which is optimal. This set forms cone, as illustrated in Fig. (middle).
x² E X2, we denote A(x*) = = E IRd x² arg min e z). We have A(x*) = {c E Rd, Vg D(x*), c 2 0}. For every 8 D(x*), we denote F(x", .8 Mxx)) ( (5)- the face of the cone A(x*) that is perpendicular to 5. Furthermore, A(x") is the dual cone of FD(""..
Proposition (Optimality Cones). For every
Notice that since X bounded, for any e E RRd, there exists x* E X such that A(x*), and consequently Rd Exx A(x*) as illustrated in Fig. (middle). Neighboring cones share boundaries corresponding to their faces (Fig- 1 right), where multiple solutions can be optimal.
F(as, 8")
F(zz,
C
Miss
303
A(aa)
A(2s)
Min
A(ax)
A(ra)
C
A(as)
M(ra)
24
F(,y,6)
Figure 1: Optimality cones relative X' (left), relative 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 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 e E C. As already restricts the location its cost vectors, our data only needs to discriminate between cones overlapping with C as illustrated in Fig. (right).
To provide further intuition, consider the example shown in Fig. (right). The set C intersects only the cones (xx²) (blue) and A(za) (green), hence, the cost vectors can only be in these two cones. Clearly, observing their projection they belong to. The set C', however, intersecting A(xx), A(xs) and A(z1), requires projections on the span of both 8' and 8". These vectors are not arbitrary; these are extreme directions that move from one cone to its adjacent cone, inducing a face where both cones intersect. The illustration highlights that such vectors are necessary to capture by our data when the face they induce intersects the uncertainty set C. Hence, it is natural to introduce the following set of relevant extreme directions. Definition 3 (Relevant Extreme Directions). Given Rd, we define
the span of 8 is sufficient to determine which of the two cones
A(X, C) R 3r XX, D(x*) and F(x", ,0) nc Ø).
In the illustration of Fig. 1 we have span A(X,C) span {8) and span A span (ō' 8"), and necessary to observe the projections on A ((X,C) C) and A(X, C') to recover optimal solutions for uncertainty sets C and C' respectively. This leads to our first main theorem.

---

Theorem 1. Let C be an open convex set. D is sufficient decision dataset for uncertainty set C and decision set X if and only if AXX C) span
Theorem D iis fundamental characterization of sufficiency, by what information the dataset needs to capture relative to the prior knowledge C and the problem structure X. The result also indicates that such minimal dataset is, in general. not unique. A careful reader might remark that Theorem [] should imply Proposition 4 when C = R In fact, A(X, IR4) is the set of all extreme directions the polyhedron, which indeed precisely spans Ker A nn Fo. Finally, remark that in the proof of the result, only convexity is required for sufficiency, while only openness required for necessity.
4.3 An Algorithmically Tractable Characterization
We now develop second characterization of dataset sufficiency that is particularly well-suited to algorithmic construction.
The set C) of relevant extreme directions of Theorem can be seen intuitively as the set of differences 21 22 of neighboring extreme points 21, 22 E X', that are optimal for some E C. By relaxing the "neighboring" condition and optimality for a common E C, we arrive a broader set of directions induced by all pairs of optimal extreme points points-which which we call reachable solutions.
Definition 4 (Reachable Solutions). Given C C RRd, we define
for
x (c) (10)= x' E Ex 3c E C, x= E arg min cT x WEX
U aEC
arg min c x. #EX
and its set of directions dir (X* (C)) == span {21 D2 22 X (C)}.
The set dir (X' (C)) is equal to the span of the set of differences between any two elements T1, 22 E X' such that there exists C1, C2 E C such that 21 E arg mingex cj x and 22 E arg minge c2 x. By construction, we have span A(X,C) C dir (X* (C)) since each relevant extreme direction corresponds to a direction between optimal solutions. The following theorem shows that these quantities are indeed equal.
Theorem 2. For any convex sel C C Rd, we have span A(X,C) = dir (X* (C)).
The converse inclusion proven in this theorem is not immediate. In fact, for general polyhedron X and C (see Fig. D with C' for eg.). A (XY C) is much smaller than the of differences of elements in X* (C) but their spans are equal. To prove the equality, we prove that for any I, x' X (C) n''', there exists a sequence of extreme points Tı..... 2y E X (C) such that #1 = x and 23 = x' and for any i E [A- 1]. 42+1 V, A(X, C). In other words, 2441, I; neighbors and are both optimal for some G E C. This implies that every element in dir (x' (C)) can be written as a finite linear combination of elements in A(X,C), completing the equality. Relating again to Proposition 4 of the case C = Rd. careful linear algebra shows that indeed dir (RR) dir (x) Ker A n Po.
Theorem implies that to construct sufficient decision dataset it suffices to find basis of dir (x* (C)) rather than span A(X, C), which is much simpler task. The following corollary will indeed be the basis of our algorithm in the next section.
Corollary 1. Let C. be an open convex set. D is sufficient decision dataset for C if and only if dir (X' (C)) C span D.
5
A Data Collection Algorithm: Finding Minimal Sufficient Datasets
We now turn to the practical problem of selecting a minimal-ia. smallest or least costly-dataset dataset D that enables generalization from prior contextual knowledge (captured by E C) to specific decision-making task (defined by X²).
In many practical settings, data collection is subject to constraints on what can be queried. We model this by restricting the dataset to lie a predefined query set @ C Rd, so that D C Q. For example, in the hiring problem discussed in Section T] Q is the set of canonical basis vectors-a data point interviewing one candidate. Corollary [ implies then that the data collection problem becomes: finding the smallest D c Q verifying dir (x' (C)) span D.
8

---

We will focus in what follows on the important case of Q being the set of canonical basis vectors. That is, each query in the data consists in evaluating one coordinate of unknown cost vector c, which represents the score of some candidate. In this case, given dir (2* (C)), represented by basis v1, - Uk,
clear that the smallest sufficient data set, verifying the spanning condition of E [d], 3j E [k), 1/ e * 0). This is all the non-zero coordinates of basis vectors of dir (X** (C)). which are required to span dir (X** (C)). This case can be generalized in straightforward manner to the case where Q is any basis of RC; see Appendix B.2
Corollary 1 is D = {e:
The central step in this approach is therefore compute dir (2 (C)) and construct basis for it, which is the focus of the remainder of this section. We can write dir (A' (C)) = span {ro x; x E X" (C)) for some 20 X (C). Hence, compute dir (A' (C)), we iteratively add elements of
while ensuring we increase the dimension at every step. This is formalized in Algorithm [
Algorithm 1 Meta- Computing dir (X* (C))
Input: Decision set X, Uncertainty set C. Output: A basis D C Rd of dir (X* (C)).
Initialize to Ø.
Set 2o arg m Cj for some cu C. while there exists E C, x² E arg min e such that x - zo span D.
D < {x* ro)- return D
The main step in Algorithm ( (condition of the while loop) can be seen verifying whether the optimization problem supf [[rrojsspan D (x* zo) || c C C, x² E arg arg migminn c x),
(2)
sEX
where (spjan D) (-) is the projection map onto (span D) has a solution with a non-zero objective. This optimization problem has two main challenges: first, it entails the inherently difficult task of maximizing convex objective, and second, it has bilinear, bi-level constraint x² E arg min e² x as both e and xt are variables and x must be an optimal solution to a linear program parameterized by
Linearizing the objective. Remark that if is a randomly generated Gaussian vector, then any vector v, with |||||| > 0, satisfies Prob(a v = 0) = O. Hence, if Problem (2) admits a solution E verifying [|proj D)- (x mo) || >> 0, then a proj D) (x vo) F 0 with probability 1, and therefore either maximizing or minimizing proj D) (x* x2) must lead to non-zero objective with probability 1. This is a linear objective as the projection onto subspace is linear.
Linearizing the bilinear, bilevel constraint. To address the second challenge, we use complementary slackness conditions, which characterize the optimal solutions of linear programs. We replace x² E arg min c² I, E C by
x² 2
0, s 2 0, A Rm CE
Ax 6, A X
z; 0, Vi E [d]
The bilinear constraint 2;3; = can be linearized by introducing a binary variable 7; E {0, and adding the constraint - Es; 2 E., with 0 small constant. When C is polyhedron, the resulting formulation is a mixed-imee inteeeerneeerrre linear program (MILP) with linear constraints and objectives.
Putting everything together gives Algorithm 2 for linear programs, which is detailed in Appendix B The algorithm will terminate in exactly dim dir (2²* (C)) iterations. When C is polyhedron, each iteration involves solving mixed integer program with O(d+m) variables and O constr((C) constraints where constr(C)) is the number of constraints defining C.
Theorem 3 (Correctness). Algorithm 2 terminates with probability 1 after dim dir (X* (C)) S d steps and outputs basis of dir (X* (C)).
6 Application: Hiring Interviews
To illustrate our insights, we apply our theoretical framework to the hiring problem detailed in Section [] The smallest sufficient dataset here is the smallest subset of candidates to interview

---

Mussecfication levt 0.2
Meuqee Flcat level: 0.7
Masppdifcatiin leval: 1.2
Naspeci leval
Vanilia
060
2.5
28
213
Experience constraiiadd
35
6.0
600
exper
clorpsioco
World expe liOc
Figure 2: Candidates to be interviewed (in red) to make an optimal hiring decision. Number of candidates interview from left right for top and bottom row respectively: 8,24, 31, 52 and 8, 28, 43, 70.
to recover the optimal hiring decision. The application illustrates how the task constraints and uncertainty set shape data needs. The goal is to hire 20 candidates from a pool of d = 100 candidates. Each candidate is associated with two features: GPA and years of experience. We study two settings: vanilla hiring, with only total hire cap, and apperience-constrainee hiring, which also limits hires per seniority group. The decision sets are Xvanilla := {x {0, 1jdd Σ 2; S 20} and Kexperience == {xr E vanillla Vj E [4], E,e,, 2; S 8J, where I, is the set of candidates with j years of experience. These constraints are totally unimodular, so relaxing
{0, 1]d to x E [o, 1] still yields optimal solutions via LP (Wolsey 2020) Chapter 3). We assume misspecified linear model, ie. candidate scores belong to
C: := {c E Rd 3a E R?, 3e E [-n,n]. esa S u, c= c + +
where 17 controls the misspecification level, and (4, 4), (5, is feature matrix whose rows are GPAs and years of experience of candidates. Fig. indicates candidates to interview enable an optimal hiring decision. Impact of C: As misspecification increases (C grows larger), so does the number of required interviews: more uncertainty requires more data points. Impact of X: In the first row Fig. 2 candidates fall into three groups: low scorers (never hired), high scorers (always hired), and mid scorers (interviewed) an intuitive pattern given the task, automatically recovered by our algorithm. When adding group hiring constraints second row of Fig. 2 a similar pattern arises, but now across experience groups rather than the entire population: low misspecification yields separate treatment between experience groups, as scores don't 't overlap across experience levels; high misspecification leads to cross-experience group comparisons and mixing- agaann, an intuitive pattern given the new constraints. Further discussion about the experiments available in Appendix D
Conclusion and Limitations
This paper introduces a framework for quantifying the informativeness of datasets in decision decision-making tasks. While our analysis yields sharp results, several natural extensions remain. First, we restrict attention to linear optimization; extending the framework other problem classes, such mixed- integer or convex programs, is an important direction even at the cost of approximate characterizations. Second, we assume query sets are basis vectors; accounting for general queries is hard problem, but opens rich avenues for exploration. Third, our focus on convex, open uncertainty sets excludes important structured cases such as low-dimensional or discrete sets encoding symmetry or logical constraints. Finally, alternative notions of informativeness, such as approximate rather than exact optimality, or noisy observations rather than clean, merit further study.
10

---

Acknowledgments and Disclosure of Funding
This work was partially supported by MIT CGC project "Preparing for a New World of Weather and Climate Extreme", and AFOSR Grant FA9550-23-1-0119.

---

References
Manish Purohit, Sreenivas Gollapudi, and Manish Raghavan. Hiring Under Uncertainty. In Proceedings of the 36th International Conference on Machine Learning, pages 5181-5189. PMLR, May 2019.
Boris Epstein and Will Ma. Selection and Ordering Policies for Hiring Pipelines via Linear Programming. Operations Research, 7265):2000-2133, September 2024. ISSN 0030-364X. doi: 10.1287/opre.02., 0061.
Rohert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposion Discrete Algorithus, SODA '05, pages 130-631. USA, January 2005. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-585.4
Alessandro Arlotto and Itai Gurvich. Uniformly Bounded Regret in the Multisecretary Problem. Stochastic Systems, 9(3)231 - September 2019. ISSN 1946-5238. doi: 10. 10.12877/tsy22018.000
Robert Bray. Does the Multisecretary Problem Always Have Bounded Regret?, December 2019.
Burr Settles. Active Learning Literature Survey. 2009.
Shuran Zheng, Bo Waggoner, Yang Liu, and Yiling Chen. Active information acquisition for linear optimization.
arXiv preprint arXiv: / 7099. 10061, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 1 edition, July 2020.
ISBN 178-1-108-571 40-1 978-1-108-48682-8 doi: 10.1017/9781 108571401.
Emil Carlsson, Dehabrota Basu, Fredrik Johansson, and Devdatt Dubhashi. Pure exploration in bandits with linear constraints. In International Conference on Artificial Intelligence and Statistics, pages 334-342.
PMLR, 2024.
Jinglong Zhao. Experimental Design for Causal Inference Through an Optimization Lens. In Tutorials in Operations Research: Smarter Decisions for Better World, INFORMS TutORials Operations Research, chapter 1, pages 146-188. INFORMS, October 2024. ISBN 979-8-988228562--5 doi: 10.1287/ educ.2004.0222
David Blackwell. Equivalent Comparisons of Experiments. The Annals Mathematical Statistics, 24(2):265- 272, 1953. ISSN 0003-4851, Jattsss:::///w jstor org/ htt/////bbeeee2333////// Publisher: Institute of Mathematical Statistics.
Henrique de Oliveira. Blackwell's informativeness theorem using diagrams. Games and Economic Behavior, 109:126-131, May 2018. ISSN 0899-8256. doi: 10.1016/j.geb.222 ge.pii/.cbb2217122.000
Cam. Comparison of Experiments: Short Review. Lecture Notex-Monograph Series, 30:127-138,
1996. ISSN 07492170. URL httt://www.jstor org/ arrgsstable/435599 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-518. Springer New York, New York, NY, 1992. ISBN 978-1-4612-4330-9. doi: 10.1007/978- 1-4612-4380-9 _5...
Frank R. Hampel, Elevezio M. Ronchetti, Peter J. Rousseeuw, and Werner A. Stahel, editors. Robust Statistics: The Approach Based on Influence Functions. Wiley Series in Probability and Mathematical Statisties Probability and Mathematical Statistics. Wiley, New York, digital print edition, 1986. ISBN 978-0-471- 73577-9.
Tamara Broderick, Ryan Giordano, and Rachael Meager. An Automatic Finite Samile Robustness Metric: When Can Dropping Little Data Make Big Differenee?, July 2023.
Amirata Ghorbani and James Zou. Data Shapley: Equitable Valuation of Data Machine Learning. In Proceedings of the 36th International Conference on Machine Learning, pages 22511 PMLR, May 2019.
Yongchan Kwon and James Zou. Beta Shapley: A Unified and Noise-reduced Data Valuation Framework for Machine Learning, January 2022.
Kevin Fu Jiang, Weixin Liang, James Zou, and Yongchan Kwon. OpenDataVal: A Unified Benchmark for Data Valuation, October 2023.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gurel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards Efficient Data Valuation Based on the Shapley Value, March 2023.
Andrew llyas. Sung Min Park, Logan Engstrom, Guillaume Leclere, and Aleksander Madry. Datamodels: Predicting Predictions from Training Data. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 9525-9587. PMIRR 2022.
Shivin Dass, Alaa Khaddaj, Logan Engstrom, Aleksander Madry, Andrew Ilyas, and Roberto Martin-Martin. DlL: Selecting Data for Robot Imitation Learning with Datamodels, May 2025.
Andrew llass and Logan Engstrom. MAGIC: Near Optimal Data Attribution for Deep Learning, April 2025.
12

---

Ittai Rubinstein and Samuel B. Hopkins. Robustness Auditing for Linear Regression: To Singularity and Beyond, October 2024.
Daniel Freund and Samuel Hopkins. Towards Practical Robustness Auditing for Linear Regression, July 2023.
Martin L. Weitzman. Optimal Search for the Best Alternative. Econometrica, 47(3))641-654, 1979. ISSN 00129682, 14680262. doi: 10.2307/1900122
Sahil Singla. The Price of Information in Combinatorial Optimization. In Proceedings of the 2018 Anmual ACM-SIAM Symposium on Discrete Algorithmss (SODA). Proceedings, pages 2523-2532. Society for Industrial and Applied Mathematics, Jamuary 2018. doi: 10.1137/1.9788 .981661 1778161175031.166 1975031.161.
Guillermo Gallego and Danny Segev. A Constructive Prophet Inequality Approach to The Adaptive ProbeMax
Problem, October 2022.
Kathryn Chaloner and Isabella Verdinelli. Bayesian Experimental Design: A Review. Statistical Science, 10(3):
273-304, 1995. ISSN 0883-4237.
Mohit Singh and Weijun Xie. Approximation Algorithms for D-optimal Design. Mathematics of Operations Research, 45(4))1512-15344 November 2020. ISSN 0364-765X. doi: 10. 20.1288/moor2201.11000
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions, June 2020.
James E Ward and Richard E Wendell. Approaches sensitivity analysis in linear programming. Annals of
Operations Research, 27 1990.
Guanglin Xu and Samuel Burer. Robust Sensitivity Analysis the Optimal Value of Linear Programming. Optimization Methods Software, 32:1 187-1205, 2017. doi: 10. 10110000055678..222 2016..2.60000
Tomas Gal and Josef Nedoma. Multiparametric linear programming. Management Science, 18(7):406-422) 1972.
Thomas Saaty and Saul Gass. Parametric objective function (part 1). Journal of the Operations Research Society of America, 2(3):316-33 319, 1954.
Utsav Sadana, Abhilash Chenreddy, Erick Delage, Alexandre Forel, Emma Frejinger, and Thibaut Vidal. A survey of contextual optimization methods for decision making under uncertainty. arXiv preprint arXiv:2306. 10374, 2023.
Yichun Hu, Nathan Kallus, and Xiaojie Mao. Fast rates for contextual linear optimization. Management Science, 68(6):4236 4245, 2022.
Dimitris Bertsimas and Nathan Kallus. From predictive to prescriptive analytics. Management Science, 66(3): 1025-1044, 2020.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1):9-26, 2022.
Mo Liu, Paul Grigas, Heyuan Liu, and Zuo-Jun Max Shen. Active learning in the predict-teen-opimmize
framework: A margin- based approach. arXiv preprint arXiv:2305.0653 2023.
Aharon Ben-Tal, Arkadi Nemirovski, and Laurent El Ghaoui. Robust optimization. 2009.
Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applications of robust optimization.
SIAM review, 53(3):44-501. 201
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, (8(3):595-612 2010.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathematical Program- ming, 167(2))235-292 2018
Aharon Ben-Tal and Arkadi Nemirovski. Robust optimization--methooolgg. and applications. Mathematical
programming, 92(3)::53-4400 2002.
Tom Rainforth, Adam Foster, Desi R Ivanova, and Freddie Bickford Smith. Modern bayesian experimental design. Statistical Science, 39(1):100-114, 14, 2024.
David Blackwell. Compurison of Recomnuissances. RAND Corporation, Santa Monica, CA, 1949.
David Blackwell. Comparison of Experiments. In Jerzy Neyman, editor, Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pages 93-102. University of California Press. 1951, ISBN 778-0-520-411588
doi: 10. 1005559978000 1586-009) 009.
S. Sherman, On Theorem of Hardy, Littlewood, Polya, and Blackwell. Proceedings of the National Academy of Sciences of the United States of America, (7(1)):226 831, 1951. ISSN 00278424, 10916490.
Charles Boll. Comparison of experiments the infinite and the of invariance in establishing suffici. PhD thesis, Stanford. 1955.
Laurence A Wolsey, Integer programming. John Wiley & Sons, 2020.
13

---

A Proofs
A.1
Proof of Proposition 2
Proof.
(+) Assume that D is sufficient decision dataset. Let c, E C such that Capan D Span We have for any q E D, c" cºqq. q. Let X given by Definition We have X (c (cTg.....,e c UN) = X (c' "c.T,...., uN) i.e. arg min cTx arg m d' x.
(+) Assume that D satisfies the property of the proposition. Since for any c, E C we have Capan D Sspan = (c" 4)4ED (d' 9)gED, then for any C, define (cT (cT...... c² qN) to be equal to arg min c' x for any d' such that Cspan D Capan
This mapping well-defined and verifies the desired property.
A.2 Proof of Proposition 3
Proof. Let Q be a matrix whose rows are the elements of D and ã(11..... 0r) E arg min (Er - (c' qi o,)2 : C). Let Qé(or..... 0r) Qume- Since i(o),..., ,r) =
arg orgmineec Qr 1o0-ol ol, then
have [Q 0,) Qrruc Ell ||e||- Hence, we have [IQE(o1,..... 0-) - Qemeel s 2 ||=|| and consequently |17l| - 2 ||Ell. We would like to show that the distance between the projections of Crue and
0,) in the span of D is upper bounded by O(IE=]). Consider Curue á R" such that E(o1...... Or)span D Q à and Crue.span D Q Oure- Without loss of generality, we can assume that is linearly independent. Indeed, if D was linearly dependent, it would provide exactly the same information any smallest cardinality subset of D that spans all elements of 'D. In this case Q is full rank and QQ is invertible. We have
Qé(oi....,,o. 0r) Qume = n Q(e(o),... ..., Or)apan D Cpuc,apan D) = 7)
QQ T (à - amne = 1) Cine (QQ
c(oi...., 0r span Cane,span D
Q-(QQ))-1n
Let U Rexe, V E Raxd and E Rexd such that U,V are orthogonal matrices and for all (1,5) E xd
o. the i-th singular value of Q if
Eij
0
else,
and Q UEVT. We have
Q QT(QQT)-1 UEVV VEVT
-UEV[UUET
VUETUTU(ETTTT = =VET -LU = VEUU
where E' E Rdxr satisfies
1 the i-th singular value of Q if
Eg
else.
Let Amin (D) the smallest singular value of Q. The calculations above gives, when ||.|| is the La norm,
2
[[eme,span S(o),...., Or) D = ||Q (QQT)~'Ql) < | (
|| S Amin (D)
||E||
We now provide essential lemma.
14

---

Lemma 1. Assume that C is open. Let D sufficient decision dataset for C C R Let e E C. There exists p > such that for any d' E such that Sspan D arg migmenex d C arg millzex c
Span pll ph we have
Proof. We assume without loss of generality that C' compact (it suffices replace by some closed ball of small radius centered around that is subset of C). Assume that the result does not hold, Lee. there exists a sequence e, such that spapan converges to Capan D. and for all n E N, there exists x' E X such that x' E arg minaex e x arg min cT x. Since the number of extreme points X are finite, there exists x' .V and a strictly increasing map y N - IN such that for all N, we have x' E arg min (p(n) arg minzex x. Since is compact, can assume without loss of generality that the sequence d' (p(n) convergent to some é' (it suffices to extract another time converging sequence from ((()). Consequently, since for all E N, (e(n)) E A(x') (see Proposition
6 for definition of A(x')), and (xx') is closed, then d' E A(x'). Furthermore, have Axx), and Capan D Span D. which means that arg mit c x arg minlge c This implies that x' arg min e Tx i.c. A(x) which is impossible.
When
|=||
(Ana( 2
we have
[Cuue,span D - .r wl1 < μ.
i.. from the lemma above, arg millee ((11,...,op) arg minsex TTe T.
A.3 Proof of Proposition
Proof. We denote F == span D. The condition Ken A C span D is equivalent to Fo Ker A ... FL, so in order to prove the equivalence with the 3rd proposition, will prove the equivalence with Fo n Ker A 1 F_d.
Assume that F+ 1 Fo Ker A. Let c' E Rd such that dp.. We will show that they have the same arg min, which proves sufficient as result Proposition 2 We show that the mapping x E X + (c (c= x is constant. In fact, for x' E X, we have
(c (c-c) (c-dd) x(-=c((((cc))
(c-c) (x (a-r) 0,
EPL
EFonker
by the assumption F+ 1 Fo n Ker A. Hence, the mappings m c x and d' x are identical in X, within a constant. Consequently, we have arg min c x arg minxex d x.
Assume that F+ Y Po n Ker A. Let c E Rd. We would like to show that there exists c' E such that OF = or and arg min cT * arg mingingex c' x. Let x' (c)c) E arg min c x. There exists a set of feasible directions for x (c). V = (81,...,,,} C (c)x, that spans Fo n Ker A (see Lemma (7). Since V spans Fu n Ker A, and F L Fo n Ker A, then there exists 5 E V such that proj (6) * 0. Let . be a positive constant and define d' -Mrroja (8). We have op cp. For all a > 0 such that x² (c) + aő E X, we have
c (x (c) + aσ) = =d
Td=T"(o (c) + acT T aMprojj (6)T
= =T x² (c) + ac - aM [|proj (5)]12
When M is be large enough, we can that we have c/ (x* (c) ad) c cT (c). which means that x² (c) arg minlge c'
Let us now prove the final part of the proposition. Let K and f: RV - X. We first prove that the set of feasible directions from & (c" q 9N) that the set of feasible directions from any extreme point spans Fg n Ker A. Let x of...., L
spans Fo n Ker A. We know from Lemma 7
15

---

and A1.... A E (0, 1] such that 2 (c" q......c'" (Tv). = =Ei=1 AeZz, For any feasible direction from x², for a > O, we have
c. qN) ad \1(x + a (c Q1 q
_ad)
1 x) ad) + Σ Aex'.
For small enough, we can see that x² ad E X' and consequently (c qIy..., cT (w)++ad X. Hence, any feasible direction from x is feasible from (c" qn...., gN). This means that the feasible directions from è (c" 91...., qN)) span Fo n Ker A. Hence, there exist ò * 0 feasible direction from (c q1....,c qN) such that 8F- * O. Cpu can take any value in F+ without changing the values of c_ "):...,C" yN. Consequently, we set Cpl -M8p1 where M is nonnegative number that we will set later. Hence, letting a > 0 such that & (c . c. qN) + E
N, we have
c. ( qI....," C. qN)N + +ad) = c q...... c qN) + acpó + =
=c f (c q..... "
c 'N)g)) + p Ma 18p111
This implies c It (c_mn.... n.,..., c. qN) + ac 5 Ma |1ăr 122 minzex T x. i.e.
a (c]gg..... Qı qu....,
TT UN) 2 -o + Ma 166pp 11 + min c x. zed
Taking M 2 K we indeed get
allóp1
T (c q c (N) 2 + min T Tx.
DE
A.4 Proof of Proposition 5
Proof. Let x" E X4. We denote J = {i E [d]. xt = 0} and Io = {i E [d]. Ex X, 2, # 0). For
every 8 E Rd, we have
E FD(x)) - Ef > 0, x= +6 0 and Ab > A6 = 0 and 6, 2 0 for every j E J.
This means that FD(z*)
) is polyhedral cone, and FD(x*) ) C Ker A. Furthermore, since [d] To C J. we also have FD(x*) C Fo which yields FD(x*) C Fy Ker A.
A.5 Proof of Proposition 6
Proof. Let x= E X'. For every c E Rd,, we have
x" arg min T x + vō FD(x"), c82 v8 D(x", c822. TEA
A.6 Proof of Theorem 1
Proof. We denote F span D. Notice that have (X F = A(X.) 1 1F1 We will now prove that D is sufficient decision dataset for C if and only if A(X F1.
(+) Suppose ((X, C) / NF-, There exists 5 E A(X, C) such that 5 y. FL, By definition, there exists I E X such that E D(x) and F(z, 8) n o Ø. Let v F(x, nc. Let 6y E FL. such that 6,
(8, exists because 5 1. F)). As C is open, we can assume without loss of generality that u+ E C by rescaling 6g We know that E F(z, 6) C A(z), and +u+ + 6o) 8
o 5 < 0 which implies that u + d0 & A(r). Finally, since we have 60 E FL, we have (e + 66)r = or + do Ur. However, v E A(x) and u + & A(x) which implies x E arg min u ' and x & arg min (v + 66) x', meaning that arg mingre (o + 5n) T o arg min o TTl. This implies that D not sufficient from Proposition
16

---

(+) Suppose D is not sufficient. From Proposition 2 there exists c, d' E C such that Op = ép and arg minzex c x * arg min c' x. It follows from the definition of the optimality cones A (Proposition 6) that there exists æ E x' such that c E A A(x) and d' A(x) (see also Lemma 6p. For any [0, 11, we denote C, = (1 a)c + ac
a² sup fa [0, 1] Ca E A(x))
sup (a [0,1] c 0, Ag e D(a)).
Since C is convex, we have car E EC. Since (xx) a closed set, we have car E A(x) and hence have cu² # c i.. a* < 1. E (0, 1 a²) small enough such that for any 8 E (()) such that Ca- T6 > 0, we have cx+ > 0. As Ca*+e & A(x), there exists e (xx) for which ca++c T8 < 0. Such ō must verify ca. 5 = 0 givee the condition defining e. Hence, Ca. E M = F(I, 8), and ca. E CC, which implies F(z, 6) & Ø and therefore 5 E A(),C). Moreover, we have (Car+e Car Car) 8 cT. te o 0. i.. 5 Y F
=o(d-
and consequently we have A(X,C) FL.
A.7 Proof of Theorem 2
Before proving the theorem, we will have to introduce a few lemmas and definition.
Lemma For any E Rd, there exists > 0 such that for any satisfying ||c dll < E, arg gi c O arg min cd +
Proof. Assume that there exists c E Rd such that for all > there exists df satisfying ||c- d'll < and arg min c x arg min c Ø. There exists a sequence (c,))eN that converges to such that for all Since there is a finite number of extreme points, there exists a subsequence (Co(n)deE and x E
IN, there exists x E X'~ \ arg min cTx x such that arg min cf x.
e X arg min cTy such that for all n E N, we have e arg mingex (p(m)8) i.c. do(n) A(x).
Hence, since ((x) is closed, we have E Mx) and x & arg minzex c which is not possible. D
Definition 5 (Extreme Point Neighbors). Let C C Rd. For any two extreme points æ1. E XX, we say that 21 and 22 are neighbors X' there exists an extreme direction ((x1) such that x2 = + 5. We say that they are C- strong neighbors in X' if furthermore there exists E C such that x. E arg mingex cTy, y.
Definition 6 (Connected and C-strongly Connected Points). For any subset y C x and C C R4, for any pair of elements x, x' E V, we say that x, x' are connected by neighboring extreme points in y if there exist h E N and a sequence I1, Ti....,. are neighbors in X and 21 = x and Ir = x'. We say that they are C-strongly connected, when T; and 1;+1 are C- strong neighbors. When there is no ambiguity, we say that x and x' are (strongly) connected.
E y such that for all i E [h - 1], and x++1
We say that the set y stronglyy connected by neighboring extreme points if this property holds for any pair of extreme points in y. When there is no ambiguity, say that (strongly) connected. For any element x of y, we call the (C (C-strong) connection class of x the set of points in y that are (c-strongly) connected by neighboring extreme points x.
Lemma 3. For any e E C, x arg min c. x is C C-strongly connected by neighboring extreme points in X.
Proof. Let E C. Every extreme point in arg min c x is also an extreme point in X' (see Lemma 6) and every extreme direction in arg mingex x is also an extreme direction X. Hence, since arg minzex c. x is bounded polyhedron, X'- minzex c is connected by neighboring extreme points X. Furthermore, by definition, since X O arg mingex e x C arg min x. then X n arg min c. x is C-strongly connected.
17

---

Lemma 4. When C is conver, X' (C) is C-stonngyy connected by neighboring extreme points.
Proof.
Assume that there ex x' E Ex (c)n that are not strongly connected. Let c' E C such that arg minlexx et y, x' arg minleex e y. For any a [0, 11, we denote eo := (1-a)ccacd Let
U= fx" E x la E [0, x² E aag ea y C X (C)
yEA
Let K be the intersection of and the connection class of a. We have x' & K. Let
C. )
a" = max E [0, K min
yEA
If a² = 1, then there exists v arg mingexx cTy y such that v K. From Lemma x n arg minyex c i C- connected and U E K n n' O narg mingex c' y and consequently x' E K, and therefore is connected to which contradicts our assumption. Hence, we necessarily have a* < 1. Furthermore, from Lemma 2 there exists e E (0, 1 - a*) such that
arg min ca n arg min c. # Ø. yEX
(3)
yEX
As K O arg min c y # and arg minzex co y stronglyy connected from Lemma 3
have arg min ca. y C K. Combined with (3), it implies that K Karrg mingex Cat+el +el + Ø. This contradicts the supremum definition of a*
We have now enough tools to prove the theorem.
Proof of Theorem We have
span (
span {a1 22 Fı, 01, E 2 nx (C), In and 22 are Stronn neighbors}
(4)
span fat 82, 01, E 2 n (C))
(5)
dir (x- nx (C))
(6)
dir (x* (C)).
Let's justify each of the equalities above.
(1) Let 8 A(X,C). There exists E C and X' such that F((x, This means that x E arg mingex T d is an extreme direction for in X, and c = 0. Consequently, there exists 1) > 0 such that x' := + nō is extreme point, that is neighbor of by definition. Also, we have x' E arg mingex c y. Hence, 8 ( z). which proves
U2 E X' nX (C), Φ1 and are C-strong neighbors). Conversely, if x1, E x x (C) are C-strong neighbors, then there exists an extreme direction for æ such that Hence, we have e = 0, and consequently E F(x1, o), which means that 5 E A(X,C) i.e. 31
C(X,C) C span {a1
Iι + 8 and E C such that 21, 32 E arg min c
x2 A(X,C). This proves the desired equality.
(2) Set Eq. 44 is clearly subset of set Eg. Let's prove the converse inclusion. Let 2, x' X nx (C). According to Lemma there exists E IN and sequence Zı, Bh E x n (C) such that x1 and Fy connected. Hence, we have
x' and for all i [/ - 1}. 2i xi+1 are C- Stronglyy
F r
Ri+1
18

---

All of the terms in the sum above are in set (4) and therefore their sum as well, by linearity. Hence, we indeed have the inclusion.
(3) This equality is immediate since for any 32 E X xx (C), 21 22 21 20
(2g 20) for any xo X nx*** (C) and consequently x1 x2 dir (x' nx* (C)).
(4) In order to prove this equality, we prove that X (C) C conv(X n n (C)). Let x E X (C) and с E C such that E arg m c y. There exists a1,...,a (0.1) an and U1...., E X such that E 1= andg. We have
such that 01
min
c y Σ age Fh i.e. Σ Caslc Ik
min c y) O. yEA'
yE
All of the terms in the sum are positive, and are consequently equal to O. Hence we have 11 E arg mingex c² y X (C). Consequently, we have conv n (C)). Hence, we have
dir (x* (C)) dir (conv(X' nx (C)))
dir (x- nx (C))
dir (x* (C)).
This proves the desired equality.
A.8 Proof of Proposition] I
Before proving the proposition, we need introduce the following lemma.
Lemma 5. For any xt E X2, there exists e Rd such that arg minze eT (x*), i.e. for all 6 E D(x*), c. > 0.
Proof. Let E X2, Assume that such a c E Rd does not exists. We first show that there exists 8* D(x*) such that A(x*) 8*, Suppose no such 8 exists, then any E D(x*), there would exist v()) E A(x*) such that T O. Consequently, we have for any D(a*),
u(8') 8'ED(r))
Σ
8>0. O.
which contradicts our initial assumption.
Let N E and 61,..., EN such that D(x*) = (ōi,..., A (x*)) 8x. Consequently, we have for all e E Rdd
5N.. Assume without loss of generality that
(Ai E (N-1), 1), 8, 2 0) = c TJ S..
We show that this implies that - NN belongs to the cone spanned by , -1 i.e. there exists .1.....
IR+ such that Σiv-1 n5d; - Assume that this is not true. Let K be the cone spanned by ..,..., 2N-1. Since -ŌN K, then (by the separation lemma), there exists that for all & E K, we have u 2 0 and -u ōN < 0. In particular, we have for all E [N - 1], 6, 2 0 and u 8 > 0, a contradiction. Hence, there exists GN-1 E R. such that
MNN1 Ain...,,N-I1
Rdd such
N ÔN
a,
Consequently, both yy and - are feasible directions from x² in X. which contradicts the fact that x² an extreme point.
We now prove Proposition I
19

---

Proof. It is easy to see that I implies We now prove that 2 implies Assume that 2 is verified but not [ that D is not a sufficient decision dataset. From Theorem X and R such that for all 5 D(x*), u 8 > 0. Let 0 such that B(c,E) C C. Let > 0 small enough such that c + M/ E Bic, E). and ry' small enough such that Cnay == + 170 1/ (spau D)- B(c, E). For any 8' D(x*), we have
there exists A C)
such that 8 L (span D)*. By definition, there exists
such that с F(x", 8).
From Lemma there exists
(c (0+) = _ +
0.
>0
This means that arg min
(c (e mu)) x= fx*). Furthermore, we have
0 =
tro 1// |0[span (D))
=0, as cEF
50, as Lispan 2)
Consequently, when is small enough compared to n/,, we have " < O, i.e. Gp.r & A(x"). This means that xx & arg minzex 2n Assume that mapping satisfying condition of the proposition. We have e + nu - Cy.a/ = 1// (epan (D)) E (span (D))+. This means that for all i E [N], we have (c (c+nu) qi = 91 and hence
+((c+ .I...., , (c T qN) 91, ..
which implies that
a( (C Q1...... T........... 9N)
(argmin c 2ex (. n (argmin( mo) mo) = Ø
which is impossible.
B Detailed Algorithm and Correction Proof
B.1 Algorithm find a basis dir (X** (C))
Algorithm 2 Computing dir (X** (C))
Input: Polyhedron x (xr
Ax b), Uncertainty set C.
Output: A basis of dir (X' (C)).
Initialize D to Ø.
Set 2o E arg min oj for some ep E C.
Sample a (N( while either of the problems
min / max a proj 2) (zo x)
s.t. x 2 0, X Rm SE R CEC
Az = b, A
1 E5; T. 2 exi Ti E (0,1) Vi
has solution x² with non-zero optimal value, D + DU {x" ro). resample a Id).
return
B.2
Full algorithm: Data Selection and Induced Decision
Here, .t...., eg is the canonical basis of Rd.
20

---

Algorithm 3 Data Selection Under Query Constraints
Input: Polyhedron X, Uncertainty Set C, Query Set Q = {42 qat (basis of Rd))
Output: A minimal sufficient dataset under constraint D Q.
Find (Ui,..., J a basis of dir (2** (C)) using Algorithm 2
Q 91, 1.....,, [d]
return D == {gs i E [d] s.t. 3j E [R], (Q 0y) e, $4000 0}.
Algorithm 4 Decision-making with a Sufficient Decision Dataset
Input: Decision set X, Uncertainty Set C. Sufficient Decision Dataset D {q....., qN Oracle such that for any q E 2, (4) c² q where e is the ground truth. Output: A decision @ E arg min x.. 01...., ON + -=)))....... (gN))
Compute è E arg min E - (c' qb o;)² c' EC}.
return å E arg min è x.
B.3
Proof of Theorem 3 Correctness
Proof.
We first show that when the algorithm terminates, i.e., the condition of the while loop is no longer satisfied, then with probability I, dir (X* (C)) span D. Notice that the constraints encode complimentary
in the minimization and maximization problems Algorithm 2
slackness and, therefore are equivalent to
min / maxfa proj(span D) (x"-zo) : c C, x² E arg mig x}.
seX
By definition of X (C), this equivalent to min max (a proj D)- (a* - -xo) x² E E (C)}. (C)).
If the two problems have an optimal value equal to O, then proj D (dir (X* (C))) T a i.c a proj 1Y (dir (X** (C)))+ Unless proj(span 2) (dir (x* (c))) Rd this set is of empty interior and its Lebesgue measure is equal 0, and consequently the probability of having projsspan 4 (dir (X* (C))) 1 a is zero since a has a continuous distribution. Hence, with probability 1, we have proj D) (dir (X (C))) = {0} i.c. dir (X** (C)) C span D.
We now show that every step of the algorithm, the dimension of the span of D in- creases by 1, and that it remains a linearly independent set, as well as satisfies span D C dir (X* (C)). Indeed, initially, DD is empty and is hence linearly independent set and satisfies span D C dir (X* (C)). Assuming that D is a linearly independent set and that span C dir (X** (C)), if there exists x E X (C) such that a proj +) (No - x)) + O, then (soj D) (xo - x) # 0 with probability 1 and consequently 2o - x e dir (X* (C))sspan D. Hence, we have dim (span (DUfzo-z))) = dim (span D) + and DU = } a linearly independent set and satisfies span (DU (20 - =)) C dir (X* (C)). which proves the desired result.
Finally, combining the two results above, when the algorithm terminates, D is a linearly dir (x" (C)) ie. D is a basis of dir (X* (C)) with proba-
independent set, and span bility 1. Furthermore, the analysis above show that the algorithm indeed terminates after dim dir (x** (C)) iterations of the while loop.
21

---

C Useful Lemmas
Lemma 6. Assume that X is bounded. For every E R arg minzex c² x is polyhedron, and all of its extreme points are extreme points in X. Recall the optimality cones A(x") of all xt E x defined in Proposition For every e, E RR, the following equivalence holds.
arg min c I = arg min cT -AE X (CE - #EX
DEX
Proof. We first show that for any E R any extreme point in arg min c_ x is in X Let E X be an extreme point of arg me e¹ x. Assume that æ is not an extreme point in X. Hence, there exists u E R such that x +
X. If + we have c (x u) < c or e c²(x + u) < <c² z. This means that & arg min c x which is impossible. If = 0, then c u E arg minzex c x, which is also impossible since x is an extreme point in arg min c x. Hence, since arg min c_ I is convex, it's the convex hull of its extreme points.
RR,, arg minrex c x = arg millgex c and only if these two sets have the same set of extreme points. Furthermore, for any X2, we have E A(x) if on and only if t E arg min c_ x. Hence, the desired result immediately follows:
Consequently, for any c,
arg min c x arg min e x + Vr E E x E Earg = x arg c' aex
zEA
aEd
ZEd
(V (x = de
Lemma Let r dim Fo Ker A. For any x E X, there exists a set V (ō1,...,8 5 C FD(x). such that V is basis of Fo n Ker A. In particular, the set of extreme directions of FD(x) spans Fo n Ker A.
Proof. Let x E X. Let X' be the set of extreme points of X, and D' be the set of extreme rays of X. For every xf X and 8 D4, we have x² 2 and 8 > 0. Let ( R and {asz bose> C R2 be a set of strictly positive numbers such that Σzexxe ag = 1. We define
Σ x EX
ax<x' + Σ a EX D'DD
E
have for any lo. H; > 0. Indeed, for any E lo. if I; -., then for every xf E X and 84 E D-, xt of 0 and hence for any x' E X, x/ = 0 i.e. & lo which is impossible. Let
=
min ,, > 0,
2 iEI
for any E Fo n Ker A such that || < E, we have A(= = AF= b. and for every i E [d] i To. then I, 6, > 0 and if & To, Iz 5, 0 and consequently direction for т. Hence, every element of B(0, $) n F. n Ker A is a feasible direction for F. and consequently any element of F2 Ker A. Let E X, and Ui,..., basis of Fo n Ker A such that for every E [r], ||::|| = 1. Let r E R small enough such that Vi E [r], I + no; E X. We would like show that for well-chosen value of y,, the following of feasible directions for s, {T - 1/01 T, ..... I + 170, x, } is a basis of Fo n Ker A. Since H - E Fo n Ker A, we consider Bi...., 8r E R such that
8 2 i.e. is feasible
T
22

---

Let 01, ar E R. We have
Σ 0s(x + you - - =0
Σ ai
(x - x) + 1
04
1=1
1=1
(AB; + 170;)11 = 0
Vi E [r], A3: + +Jo0 = 0
vi E [r]. aj = 0 or
A A and vi E [r],
0;
3 7
A
By summing over i in the last equality above, we get
= (*) - Vi =0] or AA 0 and
B
The equality above is equivalent to 1) BB Hence, it suffices to take * B and small enough to ensure that (a + 7/01 .,..., , 170, xr is linearly independent and is a set of feasible directions for x, and consequently since all of these vectors are elements of Fo n Ker A, and there are r= = dim Fo Ker of them, { + 1111 ....., T + TjU, x, } is indeed a set of feasible directions for x that is a basis of Fo n Ker A.
D Further Notes on Experiments of Section 6
Data Generation. The GPAs of candidates are generated using a uniform distribution in the interval [2, 4]. and the level of experience is also uniform in 2,, 4, 5}. The results of Fig, 2 are from applying Algorithmm] directly with the different sets C and X. The MIP Algorithm is solved using Gurobi.
Counter- of Additional Constraints in X. One would naively expect that since Xexperience smaller than Xvanilla more data would be needed to make optimal decision in the vanilla setting, but that is not necessarily true. In Fig. 2, we see that in the high misspecification regime, more data setting than the vanilla setting. In reality, the data needed
is needed for the experience-constrrinn depends on the geometry of the decision set A' relative to the uncertainty set C, as can be seen from Theorem and Corollary
Note. The hiring scenarios considered in this paper are stylized decision models intended illustrate how data informativeness depends on task structure and prior uncertainty. While some formulations include group-based constraints (e-g.. per-category quotas), these are not meant to prescribe or endorse any specific hiring policy.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The introduction makes claims each corresponding to precise results: Theo- (and corresponding section), and then rem D (and corresponding section), then Corollary |
the algorithm of Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
These are discussed in the Conclusion and Limitations Section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
24

---

Answer: [Yes]
Justification:
All theoretical results have complete proof in the appendix, and are correctly
referenced.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experiment a straightforward application of our algorithm (Algorithm B) All parameters of the LP are provided in the main text, Section and the data generation IS described in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
25

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: There is data used in the experiments. Experiments basic application of the algorithm for illustration purposes.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ httppp.ccppubcccguuuceeee Codeeubmii ssi criionPooiccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: There is not much relevant hyperparameters to the paper. Whatever is used is clearly stated.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: There no meaningful randomness the experiments. Once the data is fixed, the output is deterministic. The generated data is for illustration only, and its randomness is irrelevant the paper's claims.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: is irrelevant to the paper's results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: There is harmful or societal impact the paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There is no such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use such assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
28

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
29

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neurrs wwwptraippp..cooeeeeeeeeeeeeeeee /cc/oonfeeennes/22255 for what should or should be described.
30


Reviews:
[{"review_id": "DGvZok6FSW", "reviewer": "Reviewer_zZVt", "summary": "The paper proposes a framework to identify the minimal sufficient dataset required to solve a linear program (LP) where the cost vector is uncertain. The authors provide a geometric characterization for data sufficiency based on the problem's constraints and the uncertainty set. They further develop an algorithm based on this theory to construct such a dataset for offline data collection settings.", "questions": "1. How does the proposed methodology relate to sensitivity analysis for parametric and robust linear programming? What key theoretical contributions are novel beyond applying post-optimal analysis tools to a data sufficiency problem?\n\n2. How should a practitioner realistically define the uncertainty set $\\mathcal{C}$ for problems where the magnitude of unobserved factors is unknown beforehand? \n\n3. How to revise the experiments to better demonstrate the usefulness of the proposed methodology by addressing weaknesses points 3 and 4?", "limitations": "NA.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and easy to read.  The ''data sufficiency'' question in the offline setting is novel to me. The theoretical results are written clearly with a good pace.\n\n2. The theoretical support is rigorous. The paper provides necessary and sufficient conditions for data sufficiency, grounding the problem in the polyhedral geometry of the LP's decision space and uncertainty set.\n\n\nWeaknesses:\n\n1. $\\textbf{Overlap with sensitivity analysis.}$ The paper's main theoretical contribution appears to have overlap with established concepts in the literature on sensitivity analysis for robust LP, which is not sufficiently discussed or cited. The core theoretical mechanism of identifying \"relevant directions\" ($\\Delta(\\mathcal{X}, \\mathcal{C})$) by checking whether the uncertainty set $\\mathcal{C}$ intersects with the faces of the LP's optimality cones is a fundamental tool to post-optimal analysis. The paper's framework seems to be a re-application of these well-known principles to answer a \"data sufficiency\" question, rather than a fundamentally new theoretical discovery. \n\n2. $\\textbf{Uncertainty sets $\\mathcal{C}$.}$  The main weakness of the proposed methodology is the framework's dependence on a pre-defined uncertainty set $\\mathcal{C}$. The method's usefulness depends on the ability to specify this set, or equivalently, knowing the noise level before data collection. This is challenging in practice, as the magnitude of unobserved, \"Game-Changing\" factors is often what data collection aims to discover (see point 3 for an example). If $\\mathcal{C}$ is defined too conservatively to be safe, the method's recommendations can become trivial (i.e., collect all data).\n\n3. $\\textbf{Oversimplfied data example.}$ The paper's data example (hiring) is based on unrealistic assumptions. It implies that unobserved factors (e.g., personality, collaboration skills) have a bounded, non-decisive impact on extreme candidates (which corresponds to a high noise level regime in the paper). As stated in 2, if the unobserved factors are decisive, the method will be trivial to recommend collecting all the data.\n\n4. $\\textbf{Experimental setup inconsistent with proposed methodology.}$  There is a mismatch between the paper's theoretical treatment of noise and its experimental setup. Proposition 3 shows that with a fixed uncertainty set $\\mathcal{C}$, using data sufficiency is robust to small measurement noise $\\varepsilon$. However, the experiment takes a different approach: it constructs the uncertainty set $\\mathcal{C}$ itself by using a known, underlying \"noise level\" parameter $\\eta$. This experimental design avoids the main practical issue of how a user would define $\\mathcal{C}$ without prior knowledge of $\\eta$, thus failing to demonstrate how the framework would be applied in reality.", "was_revised": true, "final_justification": "While I acknowledge the paper is technically sound within its defined paradigm, I remain unconvinced of its practical value proposition. For these reasons, my rating will stay the same as Broadline Accept; the work is theoretically interesting, and I'm not against its acceptance, but its practical impact remains an open question.\n\nUpdated: After reviewing all the final responses the author provided, I decided to change my score to Accept. I believe it is a solid paper worth accepting.", "rebuttal": "We thank the reviewer for the efforts spent carefully reviewing our paper and providing valuable comments. Below, we address and answer in details the reviewers comments. \n\n**(Pt 1 and Q1) Connections to Sensitivity Analysis, Parametric and Robust Linear Programming.** The reviewer’s recommendation to connect our work to this literature is a very good point. Our literature review indeed focused more on the \"data part\" of the question rather than the specific aspects related to linear programming. Below we clarify how our work connects with this literature. We can include this discussion in the revised version of the paper, should the reviewer find it useful.\n\nThe goal in this stream of literature is to understand how small (sensitivity analysis, **SA**) or large (parametric programming, **PP**) changes in the LP parameters ($A$, $b$, $c$) affect the optimal value and solution (Ward and Wendell 1990). Most relevant to our setting are changes in $c$ or $b$ (since all our theory also applies to uncertainty in $b$ via the dual LP). More specifically, a typical goal is (roughly) to characterize the function $\\lambda \\to \\arg \\min_{x \\in \\cal X} c(\\lambda)^\\top x$ when the cost vector changes according to some parametrization $\\lambda \\mapsto c(\\lambda)$ within a predefined uncertainty set $\\mathcal{C} = \\{c(\\lambda): \\lambda \\in \\Gamma\\}$ (Gal and Nedoma 1972; Saaty and Gass 1954). Typically within a lower dimensional, linear parametrization. \nOur goal is different: we aim to understand what data sets (queries of the cost vector) allow recovery of the optimal solution of the LP. That is, we study how _partial information_ about the cost vector _informs_ the optimal solution, rather than how _changes_ in the cost vector _alter_ the optimal solution.\n\nThe fundamental connection is that both goals involve understanding the relationship between the cost vector $c$ and the optimal solution. Naturally, studying this interplay involves similar mathematical objects: optimality cones (analogous to critical regions in SA and PP, although slightly different) and feasible directions that change the optimality of a solution and the ones preserving it. \n\nAlthough our technical results involve similar objects, none of our results or proofs use existing results from the SA or PP literature, nor are they direct consequences of them. Below we further detail the differences in technical goals and proofs.\n\nAt the technical level, a typical question in SA is to identify the _distance to the boundary of the critical region_ (or optimality cone) along a certain direction—i.e., how much change in that direction preserves optimality. In PP, a typical goal is to _characterize all critical regions_ (or optimality cones) along some dimension, as this allows one to construct the function $\\lambda \\to \\arg \\min_{x \\in \\cal X} c(\\lambda)^\\top x$ which is piecewise constant over the (potentially exponentially many) regions.\nOur technical goal is different. Data sufficiency involves computing the _**subspace spanned by the relevant directions**_ rather than explicitly computing the optimality cones, the distances to their boundaries or the directions themselves. Relevant directions here are not all directions that change the solution, but only the most \"informative\" ones—those orthogonal to the cone faces—as these suffice to distinguish cones for our objective. There may be exponentially many such directions, data sufficiency does not require computing all of them, but only the *subspace they span*. To the best of our knowledge, this subspace has not been studied before. Our Theorem 2 is a fundamental result that allows computing it by solving at most $k$ MIPs, where $k \\leq d$ is the dimension of the subspace, rather than exhaustively enumerating all (exponentially many) relevant directions/optimality cones.\n\nAlthough we did not leverage techniques and results from SA and PP in our current paper, some of the methods developed in this rich literature for handling these mathematical objects could be useful in our context and future extensions. For instance, PP has studied problems beyond the LP case (MIPs, non-linear problems), and we could be inspired by how notions of optimality cones and directions are extended in those non-linear settings. We thank the reviewer for highlighting this connection.\n\nCitations:\n(Ward and Wendell 1990) Approaches to sensitivity analysis in linear programming\n\n(Gal and Nedoma 1972) Multiparametric Linear Programming\n\n(Saaty and Gass 1954) Parametric Objective Function\n\n**(Pt 2 and Q2) Uncertainty set $\\mathcal{C}$.** This is an important point: how should $\\mathcal{C}$ be chosen in practice? There are essentially two components in the design of the uncertainty set:\n\n*Expert knowledge.* For instance, in the hiring problem, candidate scores are non‑negative and may satisfy ratio bounds (e.g., no candidate is more than ten times better than another). In a transportation problem, edge costs are positive and upper bounded. Similarly, one may know the sign of the correlation between the score and certain features (e.g., $\\alpha_k \\ge 0$ or $\\alpha_k \\le 0$ for some feature $k$), while the “noise level” ($\\eta$ in the definition of $\\mathcal{C}$ on page 9) remains unknown.\n\n*Past data.* In addition to expert knowledge, historical data lets us build practical, data‑driven uncertainty sets via high probability confidence sets with classical statistical tools.\n\nLet us illustrate it in the hiring example. Past data would correspond to previously interviewed candidates (from earlier rounds, separate from the current pool). This means the decision maker has a set of previously observed feature vectors and associated values, $(c'_i, \\phi'_i)$ for $i\\in[N]$. \n\nLet $X\\in\\mathbb{R}^{N\\times d}$ collect past features in its rows, with $X_i^\\top=\\phi_i'$. Under the linear model $c = \\alpha^\\top \\phi + \\epsilon$ with i.i.d. Gaussian errors $\\epsilon\\sim\\mathcal{N}(0,\\sigma^2)$, the least‑squares estimator and empirical noise variance are\n  $$\n  \\hat{\\alpha}=(X^\\top X)^{-1}X^\\top c', \\qquad\n  \\hat{\\sigma}^2=\\frac{1}{N-d}\\sum_{i=1}^N (c_i'-\\hat{\\alpha}^\\top \\phi_i' )^2.\n  $$\n  A $(1-\\gamma)$ confidence interval for each coordinate $\\alpha_j$ is\n\n $$\n  \\hat{\\alpha}_j \\pm t _{1-\\gamma/2,N-d} \\sqrt{\\hat{\\sigma}^2(X^\\top X)^{-1} _{jj}}\n  $$\n\n  where $t_{1-\\gamma/2,N-d}$ is the Student‑$t$ distribution quantile. Moreover,\n  $$\n  \\frac{(N-d)\\hat{\\sigma}^2}{\\sigma^2} \\sim \\chi^2_{N-d},\n  $$\n  which yields a high‑probability upper bound on $\\sigma$ (and hence on the noise parameter $\\eta$) via the corresponding $\\chi^2$ quantile. These provide then data-driven choices for the parameters ($\\eta$, $l,u$) of the uncertainty set $\\cal C$ of page 9.\n\nThis illustrates *one* approach to designing an uncertainty set. The *robust‑optimization literature offers many ways to build $\\mathcal{C}$ from classical statistical tools*, each with different properties. More recently, conformal prediction provides distribution‑free confidence sets built from any predictive model (e.g., a neural network) to design an uncertainty set.\n\n**(Q3) As a response to Q3**, we can redesign the experiment in light of these observations by generating past data (a couple of candidates previously interviewed) and design $\\eta,u,l$ directly from that data. Then see how the data requirement changes as a function of the past data size rather than hand-chosen noise levels $\\eta$. This would give a practical case of uncertainty sets.\n\n**(Pt 3 and Q3) More on the hiring data example: impact of non-decisive features and experimental set-up.**  \nWe would like to emphasize that our algorithm does not need any assumption on the impact of unobserved factors (features). It simply determines precisely the data requirements based on whatever prior knowledge (uncertainty set) provided to it. \nIf the unobserved features are highly decisive, the algorithm will naturally recommend extensive data collection—which is exactly the correct recommendation in that case. In this case, it is fundamentally impossible to reduce the extensive data requirement, given the unobserved factors. The algorithm provides the necessary data requirement given the decision maker’s level of knowledge, whether that knowledge is rich or limited (i.e., whether uncertainty is low or high).\n\nIn our specific example, we used only two features to visually illustrate the results in a 2D plot. A realistic application would incorporate all available features. We do not impose any assumption about their informativeness; this is instead captured by $\\eta$, the noise amplitude. For different values of $\\eta$, we evaluate the resulting data requirements which naturally increases with the level of uncertainty.\n\n**(Pt 4 and Q3)  Experimental setup and misunderstanding of two different noise notions.**  \nIn point 4 of the reviewer’s comments, there appears to be confusion between two distinct notions of noise used in the paper. The noise in Proposition 3 refers, as the reviewer correctly notes, to *measurement noise*. In the experiment, this would correspond to observing an *approximate score* $c_i$ when interviewing candidate $i$, rather than the exact score. Proposition 3 states that a sufficient dataset under exact measurements remains sufficient in the presence of small measurement errors.\n\nIn the experiment section, however, what we refer to as noise ($\\epsilon$ and $\\eta$) is actually the _misspecification level_ of the linear model: measuring how informative the features $\\phi$ are (how well they predict the scores). This captures the level of uncertainty in this particular design of the uncertainty set and is a completely different concept from the measurement noise of Proposition 3. We should have explicitly referred to it as the misspecification level or uncertainty level to avoid confusion.\n\nRegarding the knowledge of $\\eta$ in the design of the uncertainty set, we detail how it can be estimated using past data in Pt2."}, {"review_id": "PkkearmPa9", "reviewer": "Reviewer_jqbm", "summary": "This paper addresses the fundamental question of how informative a dataset is for solving decision-making tasks, with a focus on linear optimization under uncertainty. It introduces a geometric framework to determine when a dataset is sufficient to recover the optimal decision, given partial information about the cost vector. The authors provide exact characterizations using relevant extreme directions and develop an efficient algorithm to construct minimal sufficient datasets. Their results demonstrate that small, carefully chosen datasets can fully determine optimal solutions, providing a principled foundation for task-aware data selection and efficient data acquisition in settings such as hiring or resource allocation.", "questions": "- I am wondering whether the framework can be extended to making-decision problems in RKHS space, Bayesian optimization or nonlinear programming? What are the challenges?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper considers an important question of ML\n\n- The paper provides conditions for when a dataset is sufficient to recover optimal decisions in linear programs. This sharp geometric formulation, based on relevant extreme directions.\n\n- The fact that the span of relevant directions for dataset sufficiency can equivalently be expressed as the span of differences between optimal solutions under different cost vectors in the uncertainty set is interesting. From this, the authors develop a practical and efficient algorithm to construct minimal sufficient datasets. \n\nWeaknesses:\n\n-  The theory assumes that the decision-maker can query arbitrary directions and observe the exact inner product. This may be a strong assumption for making decision problems I have known.\n\n-  The paper’s results apply to linear optimization where the constraint set $X$ is fully known and fixed. This can limit the generality and applicability of the framework to nonlinear programming.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent carefully reviewing our paper and for their insightful remarks. Below are our responses to the raised points in Weaknesses:\n\n- Our theory does not assume that the decision maker can query arbitrary directions. In section 4, we specify that in practice, the possible set of queries can be constrained to a set $\\mathcal Q$, and show how our algorithm can be adapted to take this constraint into account. To the reviewer's remark, we can refer to this section earlier in the paper to make that clearer. \n  As for observing the exact inner product, in fact this is a limitation in the case where measurements are noisy. Proposition 3 addresses this limitation by showing that a sufficient dataset remains sufficient with noisy measurements as long as the noise is small enough. That is, in a setting with noisy observations (noisy inner product observations), our algorithm would still output a sufficient dataset as long as the noise is small enough.\n\n- Our theory can be adapted to model the case when $\\mathcal X$ is not fixed. Indeed, for example suppose $\\mathcal X =\\\\{x\\in \\mathbb R^d, \\\\; Ax=b,\\\\; x\\geq0 \\\\}$. Uncertainty in $\\cal X$ can be modeled by either uncertainty in $b$ or in $A$. Our theory already captures uncertainty in $b$. In fact, by considering the dual of the linear program, the new cost vector becomes $b$, and our algorithm can be applied with queries on $b$ rather than on $c$. \n  However, the case of uncertainty in $A$ or jointly in $b$ and $c$ is not directly addressed by our theory, and that remains a limitation. This would be an interesting direction of work.\n\nAs for your question: The main bottleneck to adapt our theory to more general settings (RKHS, Bayesian optimization, nonlinear optimization...) is the structure of the decision set, and most importantly, the structure of the boundaries between optimality regions. The fact that optimality regions in the case of linear programming have a polyhedral structure (polyhedral cones) allows us to have a clean characterization of which queries allow us to distinguish them efficiently. This theory can be adapted by generalizing the notion to more complicated boundaries between optimality regions of other optimization problems. One promising venue for that is leveraging the theory behind Parametric Programming, which studies such optimality regions."}, {"review_id": "XrosqTaP2O", "reviewer": "Reviewer_At1w", "summary": "This paper investigates when a dataset contains sufficient information to recover the optimal solution to a linear program under cost uncertainty. The authors provide a sharp geometric characterization of task-relevant directions and propose an algorithm to construct minimal sufficient datasets. The work offers a principled perspective on task-aware data selection.", "questions": "See Weaknesses.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n- The paper addresses a fundamental and important question at the core of data-driven decision-making.\n- The theoretical contributions are a key strength. The authors establish a clean formalism and derive their results with rigorous proofs. The connection established in Thm. 2 is particularly deep and non-trivial, creating an elegant bridge from pure theory to practical application.\n- The paper is well-written, and its arguments are clear.\n\n**Weaknesses:**\n\n- The proposed algorithm relies on iteratively solving an MILP. While this is a standard and powerful approach, MILPs can be computationally intensive, and the paper lacks a detailed discussion of the algorithm's practical scalability.\n- The focus on a noiseless setting is a notable limitation. While Prop. 3 offers a valuable local robustness guarantee; the concept of \"sufficiently small\" noise would be more tangible with concrete and practical examples to illustrate its scope.", "was_revised": true, "final_justification": "I think the authors address some of my key concerns", "rebuttal": "We thank the reviewer for their insightful remarks.\n\n- As specified by the reviewer, MILPs can be computationally intensive, though they tend to perform well in practice when the problem is well structured. We mention in line 333 that the number of variables and constraints in the MILP solved at each iteration scales linearly with the dimension of the problem and the number of constraints. Hence, the size of the MILPs scales reasonably well with the size of the problem. To further substantiate our claim, we ran our algorithm for large instances of two relevant problems. The first is the vanilla hiring problem, where there were 3000 candidates, and 32 interviews were prescribed by the algorithm, which completed after roughly 8 minutes of computation. Similarly, we tested the algorithm on a shortest path problem with 1291 edges and 604 nodes. The algorithm prescribed 7 directions to query and finished running after 15 minutes. These experiments were conducted on a regular laptop, which illustrates that the practical computational complexity scales reasonably with the problem size. However, it is true that for significantly larger instances (in the order of $>10^5$ variables), solving the MILPs may become more challenging.\n- This is indeed a valid point. In Proposition 3, we prove that when the noise level is low enough, then a sufficient dataset still recovers the optimal solutions. In order to quantify the change in optimality beyond what is covered by proposition 3, we extend this result: when the noise amplitude exceeds the threshold $\\kappa$, the normalized optimality gap scales linearly with the noise magnitude. More precisely, we can prove that if $c_{True}$ is the true cost vector, $o$ is the vector containing query observations, and $\\varepsilon$ is a real-valued vector, $\\hat{x}(o+\\varepsilon)$ the decision inferred by our algorithm given noisy observations $o+\\varepsilon$, and $x^\\star$ the optimal decision for the cost $c_{True}$, then we have $c_{True}^\\top \\hat{x}(o+\\varepsilon) - c_{True}^\\top x^\\star = O(||\\varepsilon||)$ if $||\\varepsilon||$ exceeds some threshold $\\kappa > 0$, and $c_{True}^\\top \\hat{x}(o+\\varepsilon) - c_{True}^\\top x^\\star = 0$ otherwise. This demonstrates that, in the worst case, the error introduced by our algorithm scales linearly with the noise amplitude."}, {"review_id": "w303xN6J2h", "reviewer": "Reviewer_6K14", "summary": "The goal is to choose  $x$ to minimize a loss function $L(x,\\theta)$, where $\\theta$ is a fixed but unknown parameter. Since $\\theta$. is not known, they evaluate the loss at N points to estimate $\\theta$. This paper considers the setting where the function $L$ is linear and the decision variable $x$ has to be selected from a polyhedral set. It is also assumed that the parameter $\\theta$ comes from a given uncertainty set. The authors introduce the notion of a sufficient dataset, defined as a collection of $N$ objective functions that allow exact recovery of the true optimal solution. The paper proposes an algorithm for finding minimal sufficient dataset for this problem.", "questions": "- Can you provide another use case, which actually solves an LP optimization problem?\n\n- What you want to show in Figure 2?", "limitations": "Yes", "rating": 2, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 1, "originality": 4, "strengths_and_weaknesses": "- The problem setting is difficult to understand and not clearly explained. Initially, the paper states that the parameter $\\theta$ is not known. But later the concept of prior contextual knowledge is introduced.   \n\n- The example based on the Secretary Problem is difficult to follow. If $\\phi$ represents resumes of the candidates, what does $\\theta$ represent?   Also, in the Secretary Problem, the decision space increases as more candidates are interviewed, whereas the formal problem setup in Section 2 assumes a fixed-dimensional decision space $\\chi \\in \\mathcal{R}^d$. \n\n-  Algorithm 1 proposes a meta-algorithm that solves the LP optimization problem for every possible parameter value and stores all the unique solutions. This seems to be a trivial way to implement and I do not see the novelty. Indeed, if one could enumerate all possible solutions, the LP problem can be solved. Moreover, in most LP problems, the parameter space is continuous, making it unrealsistic to solve the LP for every possible parameter value $c$. \n\n- In general, the paper lacks consistent focus. It begins with the motivation of defining the informativeness of a dataset for solving an optimization problem, but this idea is not mentioned in Sections 3 and 4. As a result, the narrative loses a clear goal  and seems disconnected from the motivation in the Introduction. \n\n- I feel that the theoretical framework introduced in the earlier sections does not align well with the Secretary Problem use case. In the Secretary Problem, it is unclear what the basis vector of a solution would be. Additionally, LP solutions can be characterized by the extreme points (vertices) of the feasible region. So, if one stores all the vertices, the LP solution is guaranteed to come from this set. However, one cannot make a similar claim for the Secretary Problem. There is no guarantee that the best candidate will come from a predefined set of candidates.  Therefore, in my opinion, the Secretary Problem does not fit well with the problem formulation. \n\n- There is only one experiment, not sufficient for empirical evaluation. Moreover, the setup is not clearly explained. it is not immediately clear what the authors want to highlight in Figure 2.", "was_revised": true, "final_justification": "- I sincerely thank the authors for addressing my question during the rebuttal. Their answers helped me better understand the proposed technique. However, they also brought into focus what I see as the main weakness of the paper -- a lack of a clear problem definition with motivating example(s). Rather than starting with a concrete, well-motivated example, the paper opens with unrelated topics such as LLMs.   Because of this the paper fails to convince readers about the significance of the proposed approach. \n\n- Similarly, the literature review does not connect clearly to linear programming. It is not addressed why  approaches -- such as predict-then-optimize or robust optimization -- are insufficient for the kind of problems they are tackling. \n\n- Finally,  in their final remarks, the authors note: \"We believe to be the first to address such a problem. Therefore, there are no baseline competitors to compare with.\" This statement also suggests that the problem as defined is not being addressed in practice, raising questions about its significance.\n\nI believe the paper requires a revision providing a well-defined problem statement, clear motivation supported by a relevant example, and a focused discussion that avoids unrelated topics. However, given that this would require substantial restructuring, I must maintain my recommendation for rejection.", "rebuttal": "There is a substantial misunderstanding of the concepts in the paper from the reviewer.  Several of the point mentioned by the reviewer are based on a wrong understanding of parts of the paper. In what follow we clarify the concepts and misunderstandings as a response to each point in the \"Strengths and Weaknesses\" and the Questions.\n\nOn the points raised in \"Strengths and Weaknesses\":\n\n1- The parameter $\\theta$ is indeed not known, and this is consistent throughout the paper. Prior knowledge does not contradict that. $\\theta$ is not fully known, but belongs to an uncertainty set, which models prior knowledge. \n\nThe parameter $\\theta$ is introduced for the first time in Line 32, directly as \"an unknown parameter $\\theta \\in \\Theta$\". That is $\\theta$ in unknown, but belongs to a set $\\Theta$. Soon afterwards (Line 35) refers to the set $\\Theta$ as prior knowledge: \"The decision-maker can then use the observations along with their prior knowledge (set restriction $\\theta \\in \\Theta$)\".  \n\n2- In the example of the Secretary Problem, $\\theta$ represents the values of the candidates. In the paragraph that introduces the example, in the first time where $\\theta$ is mentioned (Line 53) it reads \"Each candidate has an unknown value $\\theta_i$\". \n\nIn the Secretary Problem, **it is not correct that the decision space increases as more candidates are interviewed**. In the Secretary Problem, the decision space $\\cal X \\subset \\\\{0,1\\\\}^d$ (Line 50), that is each decision is a binary vector, of which each coordinate correspond to one given candidate. The binary coordinate $x_i$ indicates whether candidate $i$ is hired or not: this is the decision in the problem. The decision space is therefore fixed here and does not change with more candidates interviewed. It is of dimension $d$, the number of available candidates (one dimension per candidate). An interviewing decision (a query $q_i$ revealing $\\theta^\\top q_i = \\theta_i$, the value of candidate $i$) does not change the decision set $\\cal X$ if this is what the reviewer means. \n\n3- **It is not correct that Algorithm 1 consists of solving the LP for every possible value of c.** The paragraphs following Algorithm 1 describes how we implement the meta algorithm and Algorithm 2 provides a detailed version. The algorithm does not solve the original LP and certainly not for every value of $c$. It solves iteratively integer programs outputting the smallest basis spanning the relevant extreme directions of Theorem 2 and Theorem 1. It runs in at most $d$ iterations, where $d$ is the dimension of the problem as explicitly stated in Theorem 3. More precisely it runs in $k$ steps, $k$ being the dimension of the subspace spanned by relevant extreme directions.\n\n4- Following the motivation and discussion around informativeness, we specify in the introduction, contribution paragraph, that \"We study informativeness in the sense of being able to recover the task’s optimal solution\" (Line 107).  Section 2 then mathematically models this question by the notion of a \"*sufficient data set*\" which is the focus of the paper. The subsequent sections focus on the technical resolution of this question, providing precise characterizations and an algorithm for identifying informative datasets in that sense. \n\n5- We respond to the two parts of this remark separately: \n\n- Could the reviewer clarify what \"the basis vector of a solution\" means? If the reviewer's question is about basis vectors is the set of possible queries $\\mathcal Q$ (Line 304), then these are $(e^1,\\ldots,e^d)$ where $e^i_i=1$ and $e^i_j = 0$ for $i\\neq j$ (indicator vectors). A decision $x=e_i$ corresponds to hiring candidate $i$  and no other candidate. A query $e_i$ corresponds to interviewing candidate $i$ as it reveals its value $\\theta^\\top e_i = \\theta_i$. We explain these in paragraph introducing the Secretary Problem (Line 49), where we specify that the decision variable is binary shows which candidates are hired, and explains that interviewing a candidate means observing the coordinate of $\\theta$ that specifies the score of the candidate (i.e. querying a vector from the canonical basis). \n\n- **The Secretary Problem is in fact mathematically a linear program** as explained in the introduction. It is solving $\\min_{x \\in \\cal X} \\theta^\\top x$ where the constraint set is specified by linear constraints $\\cal X \\subset [0,1]^d$. This is also a well known result in the Secretary Problem literature on the Offline Secretary Problem. Its solutions are extreme point of this polyhedron (verifying $x \\in \\\\{0,1\\\\}^d$) which corresponds to a hiring decision (which candidate to hire). **The best hiring decision will in fact be an extreme point.** In our paper, we introduce a relevant version of the multi-secretary problem that is offline, i.e. all candidates have already applied and the recruiter has to choose the best candidates.\n\n\n6- Could the reviewer specify what is unclear about the experimental set-up and the discussion around Figure 2? \nThe setup is that we have a set of candidate providing their GPA and a number of years of experience. We run our algorithm to decide which candidates to interview. The last paragraph of the experiment section specifically describes what we observe in Figure 2.  It illustrate how the optimal set of interviews (output of our algorithm) changes with the uncertainty and the hiring constraints.\n\nResponse to Questions:\n\n1- The reviewer's question seems to suggest that the Secretary Problem is not an LP. We would like first make it clear that the Secretary Problem is in fact an LP, as we discussed in response 5. We explicit that in the introduction and the experimental set up (Page 9, line before 340). It is also a very well known (and immediate) result in the Secretary Problem literature. \n\nTo respond to the reviewer's question, another very relevant setting to our framework is the shortest path problem, which can be cast as a linear program. Assume for example that after an earthquake, emergency responders need to find the shortest path to an area to deliver important first aid resources, or launch a rescue operation, and can only check a limited number of routes. Assuming emergency responders have correlated data to the difficulty of each route, our algorithm can be used to specify which roads should be explored to find the shortest path for the delivery or/and rescue.\n\n\n2- In Figure 2, we show how uncertainty and hiring constraint affect the optimal set to be interviewed. More uncertainty implies more candidates to interview and hiring constraints impact the interviews in a subtle way. The last paragraph of Section 5 discusses Figure 2 in details."}]

Author rebuttal:

Meta-review: This paper studies linear programs where problem parameters are unknown and lie in an uncertainty set. Given a dataset that provides information about these parameters, the paper characterizes when this dataset is sufficient to identity an optimal solution.

The strength of this paper is that it is a clearly-written theory paper studying a novel question of data informativeness in the context of an important problem class (linear programs).

Much of the discussion centered around aspects of linear programming and robust optimization that stem from the novelty of these techniques within the NeurIPS community.  The authors handled these points well in their rebuttal. Let me list some of them:
- Questions about the novelty of the analysis relative to work on sensitivity analysis.  As the authors explain, both this paper and works on sensitivity analysis use similar technical tools, but this doesn't significantly detract from the paper's novelty.
- Concerns about how to choose the uncertainty set. As the authors explain in their rebuttal, this is a well-studied question in the robust optimization literature and the authors should not be faulted for this concern.
- The work does not study nonlinear programs. I do not view this as a problem. There are many important problems that can be formulated as linear programs.

The reviews also raised points that I view as real weaknesses. I list them here:
- Computational cost of solving many MILPs. The authors point out that there are many problems where the cost would be acceptible, and that the number of MILP variables and constraints have a reasonably benign scaling. Thus, while this is a limitation, there are still many problems where the proposed method could be useful.
- The paper's results focus on the noiseless setting and become more limited when there is noise.

Reviewer 6K14 rated the paper "2 reject" but the reasons cited seem to stem from a difficulty understanding the paper and not from a weakness in the paper itself. While there are always opportunities to improve clarity in a paper, the writing in this paper is reasonably clear. Instead, the low score seems to stem from the fact that linear programming is not well known to many reviwers at NeurIPS. I view bringing ideas from linear programming to NeurIPS as a strength of this paper, not a weakness, and so I am discounting 6K14's rating.
Decision: Accept (poster)