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

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.

On the points raised in "Strengths and Weaknesses":

1- 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.

The 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$)".

2- 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$".

In 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.

3- 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.

4- 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.

5- We respond to the two parts of this remark separately:

• 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).

• 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.

6- Could the reviewer specify what is unclear about the experimental set-up and the discussion around Figure 2? The 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.

Response to Questions:

1- 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.

To 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.

2- 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.

where $\theta_i$ is the value of candidate $i$ and $k$ is the number of candidates we want to hire. Because of total unmodularity, the variable $x_i$ will always be $0$ or $1$ at optimum. Therefore $x_i\in\\{0,1\\}$ models whether we hire candidate $i$ ($x_i=1$) or not $(x_i=0)$. The constraints ensure we do not hire more than $k$ candidates. We can cast the problem as a minimization problem, by simply flipping the sign. 
$$

\min_x & \\; -\theta^\top x \\
&0\leq x_i \leq 1, \\; \forall i\\
&\sum_{i=1}^d x_i \leq k

We thank the reviewer for their insightful remarks.

• 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.
• 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.

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:

• 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. 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.

• 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$. 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.

As 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.

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.

(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.

The 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. Our 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.

The 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.

Although 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.

At 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. Our 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.

Although 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.

Citations: (Ward and Wendell 1990) Approaches to sensitivity analysis in linear programming

(Gal and Nedoma 1972) Multiparametric Linear Programming

(Saaty and Gass 1954) Parametric Objective Function

(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:

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.

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.

Let 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]$.

Let $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

$$\hat{\alpha}=(X^\top X)^{-1}X^\top c', \qquad \hat{\sigma}^2=\frac{1}{N-d}\sum_{i=1}^N (c_i'-\hat{\alpha}^\top \phi_i' )^2.$$

A $(1-\gamma)$ confidence interval for each coordinate $\alpha_j$ is

$$\hat{\alpha}_j \pm t _{1-\gamma/2,N-d} \sqrt{\hat{\sigma}^2(X^\top X)^{-1} _{jj}}$$

where $t_{1-\gamma/2,N-d}$ is the Student‑$t$ distribution quantile. Moreover,

$$\frac{(N-d)\hat{\sigma}^2}{\sigma^2} \sim \chi^2_{N-d},$$

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.

This 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.

(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.

(Pt 3 and Q3) More on the hiring data example: impact of non-decisive features and experimental set-up.
We 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. If 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).

In 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.

(Pt 4 and Q3) Experimental setup and misunderstanding of two different noise notions.
In 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.

In 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.

Regarding the knowledge of $\eta$ in the design of the uncertainty set, we detail how it can be estimated using past data in Pt2.

Thank you for your detailed response. Your clarifications regarding the distinction from sensitivity are well-taken and helpful. I recommend integrating these discussions into the revised manuscript.

However, your response has confirmed my primary concern regarding the paper's real-world significance.

The proposed solution for defining the uncertainty set C, by using statistical confidence sets from past data, exposes a fundamental, philosophical weakness. By offloading the most challenging part of the problem (characterizing uncertainty) to a standard statistical procedure, the robust optimization framework becomes a deterministic step applied to a probabilistic basis. This raises the question: why is this two-stage, hybrid approach superior to a more integrated, fully statistical framework (e.g., Bayesian decision theory) that handles both uncertainty estimation and decision-making coherently under a single probabilistic roof?

The simplified examples emphasize this concern. For the methodology to work smoothly, the problem must be reduced to a "toy" version where the uncertainty is manageable and clearly bounded. This does not convince me of the method's usefulness for complex problems, where the main challenge is understanding the nature of the uncertainty itself.

Therefore, 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.