Data Informativeness in Linear Optimization under Uncertainty

Omar Bennouna, Amine Bennouna, Saurabh Amin, Pablo A. ParriloarXiv 2026 · DOI · arXiv

TL;DR

This paper shifts the focus of data collection from "estimating parameters" to "making the right decision." By providing a geometric characterization of "data sufficiency," the authors show how to identify the smallest possible dataset needed to solve a specific linear optimization task, proving that we often need far less information than full parameter estimation would suggest.

What Problem Does This Paper Address?

In many real-world scenarios—from infrastructure planning to hiring—we have to make decisions based on parameters we don't fully know (like construction costs or a candidate's future performance). The standard "estimation-focused" paradigm is to collect as much data as possible to estimate these parameters accurately and then optimize.

However, data collection is expensive and time-consuming. The authors argue that we don't actually need to know every parameter perfectly; we only need enough information to distinguish which decision is optimal. For example, if you are building a subway line between two northern neighborhoods, you don't need to know the exact soil conditions in the south of the city. This paper formalizes this "decision-focused" view, asking: What is the minimum data required to guarantee we find the optimal solution for a specific task?

Methods

The authors focus on Linear Programs (LPs) where the cost vector $c$ is unknown but belongs to a known uncertainty set $C$. Their approach is built on three pillars:

  1. Decision-Focused Informativeness: They define a dataset as "sufficient" if there exists any algorithm that can recover the optimal decision using only that data and prior knowledge. This abstracts away the specific estimator used.
  2. Geometric Characterization: The core theoretical contribution is proving that a dataset is sufficient if and only if it spans a specific task-relevant subspace. They show this subspace is equivalent to the span of the differences between optimal solutions ("reachable solutions") across all possible cost vectors in the uncertainty set.
  3. Tractable Algorithms: To make this practical, they develop Algorithm 2, which computes this task-relevant subspace. It uses Mixed-Integer Linear Programming (MILP) to navigate the "optimality cones" of the feasible region. They also provide algorithms to find the smallest set of queries (minimal datasets) under various constraints (e.g., when you can only observe individual coordinates or when queries must come from a specific convex set).

Datasets

The paper evaluates its framework using two primary applications:

  • Minimal Cost Subway Line Design: This uses a real-world neighborhood graph map from the United States. The task is a shortest-path problem where edge costs (construction expenses) are uncertain.
  • Hiring Interviews: A synthetic dataset of 100 candidates, each with features like GPA and years of experience. The "value" of a candidate is modeled using a misspecified linear model, and the task is to select the best subset of candidates to hire under various organizational constraints.

Key Insights and Ideas

  • The "Aha" Moment on Cycles: In network flow problems (like the subway example), the authors found that the most informative data points naturally form cycles. This makes intuitive sense: to know if Path A is better than Path B, you need to measure the "loop" that connects them to compare their relative costs.
  • Structure Over Accuracy: Informativeness depends as much on the constraints of the problem as it does on the uncertainty of the parameters. A new constraint might make previously vital data irrelevant, or vice versa.
  • Continuous vs. Discrete Query Sets: The authors show that finding the smallest dataset is NP-hard for general discrete query sets (like picking specific edges in a graph). However, if the query set has continuous geometric structure (like a vector space or a convex set), the problem becomes solvable in polynomial time.
  • Sufficiency is Estimator-Independent: By defining sufficiency based on the existence of a mapping, the framework identifies the intrinsic value of the data itself, regardless of whether you use a simple linear regression or a complex neural network to process it.

Key Results

  • Theoretical Tightness: The authors provide a necessary and sufficient condition (Theorem 1) for data sufficiency in relatively open convex uncertainty sets.
  • Efficiency in Practice: In the subway application, the algorithm correctly identifies that as uncertainty ($\epsilon$) increases, the required data size grows. At low uncertainty, only a few strategic edges need to be inspected to guarantee an optimal route.
  • Hiring Insights: The hiring model demonstrates that "vanilla" hiring (just a cap on total hires) often requires different data than "constrained" hiring (quotas for seniority). Surprisingly, more constraints don't always mean you need more data; sometimes, constraints narrow the search space so much that less data is needed to find the optimum.

Limitations and Future Work

  • Beyond Linear Programming: The current framework is strictly for LPs. While the authors prove some extensions for Mixed-Integer Programs (MIPs), extending the geometric characterization to general non-linear convex optimization remains an open challenge.
  • Uncertainty in Constraints: The model assumes uncertainty lives in the objective function (the costs). In many problems, the uncertainty is in the constraints themselves (the $A$ matrix), which would require a different geometric treatment.
  • Computational Scaling: The algorithm for finding the task-relevant subspace relies on solving MILPs. While efficient for moderate sizes, very large-scale industrial problems might require more specialized solvers or heuristic approximations.
  • Stochastic Observations: The primary focus is on noiseless data. While the authors provide a proposition for noisy measurements, a deeper exploration of the trade-off between "number of samples" and "optimality gap" is noted as a direction for future research.

Summary updated

Abstract

We study the problem of determining what data is required to solve a decision-making task when only partial information about the state of the world is available. Focusing on linear programs, we introduce a decision-focused notion of data informativeness that formalizes when a data set is sufficient to recover the optimal decision. Our notion abstracts away the notion of estimators (how data is used): it depends solely on the structure of the optimization task and the uncertainty. Our main result provides a geometric characterization of data sufficiency: a data set is sufficient if and only if, together with prior knowledge, it captures all cost directions that can change the optimal solution, given the task structure and the uncertainty set. Building on our characterization, we develop a tractable algorithm to determine minimal sufficient data sets under general data collection constraints. Taken together, our work introduces a principled framework for task-aware data collection. We demonstrate the approach in two applications: selecting where to conduct field experiments to inform infrastructure design and choosing which candidates to interview in order to make an optimal hiring decision. Our results illustrate that small, carefully selected data sets often suffice to determine the optimal decisions.
BibTeX
@misc{bennouna2026data,
  author = {Omar Bennouna and Amine Bennouna and Saurabh Amin and Pablo A. Parrilo},
  title = {{Data Informativeness in Linear Optimization under Uncertainty}},
  year = {2026},
  eprint = {2602.15365},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.15365},
}

Loading related content...

Figure