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

• URL: http://arxiv.org/abs/2505.21692v1
• Date: Tue, 27 May 2025 19:28:22 GMT
• Title: What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
• Abstract summary: We study the fundamental question of how informative a dataset is for solving a given decision-making task.<n>We characterize when a dataset is sufficient to recover an optimal decision, given an uncertainty set on the cost vector.<n>Our results reveal that small, well-chosen datasets can often fully determine optimal decisions.
• Score: 3.124884279860061
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Learning Polyhedral Conformal Sets for Robust Optimization [10.504036065018216]
  We propose a decision-aware conformal framework that learns uncertainty sets tailored to robust optimization objectives.<n>Our approach parameterizes a flexible family of polyhedral sets via data-driven hyperplanes and learns their geometry by directly minimizing the induced robust loss.<n>We provide finite-sample coverage guarantees and bounds on the sub-optimality gap to an oracle decision.
  arXiv  Detail & Related papers  (2026-05-08T21:39:41Z)
• OPO: Making Decision-Focused Data Acquisition Decisions [0.0]
  We propose a model for making data acquisition decisions for variables in contextual optimisation problems.<n>We solve the data acquisition problem with well-defined constraints by learning a surrogate linear objective function.<n>We ablate the problem with a number of training modalities and demonstrate that the differentiable optimisation approach outperforms random search strategies.
  arXiv  Detail & Related papers  (2025-04-21T12:41:35Z)
• Unifying and Optimizing Data Values for Selection via Sequential-Decision-Making [5.755427480127593]
  We show that data values applied for selection can be reformulated as a sequential-decision-making problem.<n>We propose an efficient approximation scheme using learned bipartite graphs as surrogate utility models.
  arXiv  Detail & Related papers  (2025-02-06T23:03:10Z)
• Compute-Constrained Data Selection [77.06528009072967]
  We find that many powerful data selection methods are almost never compute-optimal.<n>For compute-optimal training, we find that perplexity and gradient data selection require training-to-selection model size ratios of 5x and 10x, respectively.
  arXiv  Detail & Related papers  (2024-10-21T17:11:21Z)
• LESS: Selecting Influential Data for Targeted Instruction Tuning [64.78894228923619]
  We propose LESS, an efficient algorithm to estimate data influences and perform Low-rank gradiEnt Similarity Search for instruction data selection. We show that training on a LESS-selected 5% of the data can often outperform training on the full dataset across diverse downstream tasks. Our method goes beyond surface form cues to identify data that the necessary reasoning skills for the intended downstream application.
  arXiv  Detail & Related papers  (2024-02-06T19:18:04Z)
• DsDm: Model-Aware Dataset Selection with Datamodels [81.01744199870043]
  Standard practice is to filter for examples that match human notions of data quality. We find that selecting according to similarity with "high quality" data sources may not increase (and can even hurt) performance compared to randomly selecting data. Our framework avoids handpicked notions of data quality, and instead models explicitly how the learning process uses train datapoints to predict on the target tasks.
  arXiv  Detail & Related papers  (2024-01-23T17:22:00Z)
• Experiment Planning with Function Approximation [49.50254688629728]
  We study the problem of experiment planning with function approximation in contextual bandit problems. We propose two experiment planning strategies compatible with function approximation. We show that a uniform sampler achieves competitive optimality rates in the setting where the number of actions is small.
  arXiv  Detail & Related papers  (2024-01-10T14:40:23Z)
• Data-Driven Offline Decision-Making via Invariant Representation Learning [97.49309949598505]
  offline data-driven decision-making involves synthesizing optimized decisions with no active interaction. A key challenge is distributional shift: when we optimize with respect to the input into a model trained from offline data, it is easy to produce an out-of-distribution (OOD) input that appears erroneously good. In this paper, we formulate offline data-driven decision-making as domain adaptation, where the goal is to make accurate predictions for the value of optimized decisions.
  arXiv  Detail & Related papers  (2022-11-21T11:01:37Z)
• Online Coreset Selection for Rehearsal-based Continual Learning [65.85595842458882]
  In continual learning, we store a subset of training examples (coreset) to be replayed later to alleviate catastrophic forgetting. We propose Online Coreset Selection (OCS), a simple yet effective method that selects the most representative and informative coreset at each iteration. Our proposed method maximizes the model's adaptation to a target dataset while selecting high-affinity samples to past tasks, which directly inhibits catastrophic forgetting.
  arXiv  Detail & Related papers  (2021-06-02T11:39:25Z)
• Data-Driven Combinatorial Optimization with Incomplete Information: a Distributionally Robust Optimization Approach [0.0]
  We analyze linear optimization problems where the cost vector is not known a priori, but is only observable through a finite data set. The goal is to find a procedure that transforms the data set into an estimate of the expected value of the objective function.
  arXiv  Detail & Related papers  (2021-05-28T23:17:35Z)
• Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization [12.610576072466895]
  This work addresses inverse linear optimization where the goal is to infer the unknown cost vector of a linear program. We introduce a new formulation of the problem that, compared to other existing methods, allows the recovery of a less restrictive and generally more appropriate admissible set of cost estimates.
  arXiv  Detail & Related papers  (2020-09-16T22:25:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.