Computational Budget Should Be Considered in Data Selection

• URL: http://arxiv.org/abs/2510.16806v2
• Date: Sun, 02 Nov 2025 08:01:37 GMT
• Title: Computational Budget Should Be Considered in Data Selection
• Authors: Weilin Wan, Weizhong Zhang, Cheng Jin,
• Abstract summary: We argue that compute budget must be integral to data-selection strategies.<n>We propose a novel Computational budget-Aware Data Selection (CADS) method.<n>Our method achieves performance gains of up to 14.42% over baselines in vision and language benchmarks.
• Score: 21.598075666695483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Data selection improves computational efficiency by choosing informative subsets of training samples. However, existing methods ignore the compute budget, treating data selection and importance evaluation independently of compute budget constraints. Yet empirical studies show no algorithm can consistently outperform others (or even random selection) across varying budgets. We therefore argue that compute budget must be integral to data-selection strategies, since different budgets impose distinct requirements on data quantity, quality, and distribution for effective training. To this end, we propose a novel Computational budget-Aware Data Selection (CADS) method and naturally formulate it into a bilevel optimization framework, where the inner loop trains the model within the constraints of the computational budget on some selected subset of training data, while the outer loop optimizes data selection based on model evaluation. Our technical contributions lie in addressing two main challenges in solving this bilevel optimization problem: the expensive Hessian matrix estimation for outer-loop gradients and the computational burden of achieving inner-loop optimality during iterations. To solve the first issue, we propose a probabilistic reparameterization strategy and compute the gradient using a Hessian-free policy gradient estimator. To address the second challenge, we transform the inner optimization problem into a penalty term in the outer objective, further discovering that we only need to estimate the minimum of a one-dimensional loss to calculate the gradient, significantly improving efficiency. Extensive experiments show that our method achieves performance gains of up to 14.42% over baselines in vision and language benchmarks.

Related papers

• Labels or Preferences? Budget-Constrained Learning with Human Judgments over AI-Generated Outputs [17.028710603629026]
  We show how to optimally allocate a fixed annotation budget between ground-truth labels and pairwise preferences in AI.<n>We introduce Preference-Calibrated Active Learning (PCAL), a novel robustness method that learns optimal data acquisition strategy.<n>This work provides a principled and statistically efficient approach for budget-constrained learning in modern AI.
  arXiv  Detail & Related papers  (2026-01-19T23:23:29Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Data Selection for ERMs [67.57726352698933]
  We study how well can $mathcalA$ perform when trained on at most $nll N$ data points selected from a population of $N$ points.<n>Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression.
  arXiv  Detail & Related papers  (2025-04-20T11:26:01Z)
• Self-Steering Optimization: Autonomous Preference Optimization for Large Language Models [79.84205827056907]
  We present Self-Steering Optimization ($SSO$), an algorithm that autonomously generates high-quality preference data.<n>$SSO$ employs a specialized optimization objective to build a data generator from the policy model itself, which is used to produce accurate and on-policy data.<n>Our evaluation shows that $SSO$ consistently outperforms baselines in human preference alignment and reward optimization.
  arXiv  Detail & Related papers  (2024-10-22T16:04:03Z)
• 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)
• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  Policy evaluation via Monte Carlo simulation is at the core of many MC Reinforcement Learning (RL) algorithms. We propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths. We present an adaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO)
  arXiv  Detail & Related papers  (2024-10-17T11:47:56Z)
• Speeding-up Evolutionary Algorithms to solve Black-Box Optimization Problems [0.0]
  Population-based evolutionary algorithms are often considered when approaching computationally expensive black-box optimization problems. We propose a technique capable of choosing an appropriate approximate function cost during the execution of the optimization algorithm. The proposal finds the minimum evaluation cost at which the solutions are still properly ranked, and consequently, more evaluations can be computed in the same amount of time with minimal accuracy loss.
  arXiv  Detail & Related papers  (2023-09-23T11:54:46Z)
• Efficient Learning of Decision-Making Models: A Penalty Block Coordinate Descent Algorithm for Data-Driven Inverse Optimization [12.610576072466895]
  We consider the inverse problem where we use prior decision data to uncover the underlying decision-making process. This statistical learning problem is referred to as data-driven inverse optimization. We propose an efficient block coordinate descent-based algorithm to solve large problem instances.
  arXiv  Detail & Related papers  (2022-10-27T12:52:56Z)
• Trajectory-based Algorithm Selection with Warm-starting [2.3823600586675724]
  We study the quality and accuracy of performance regression and algorithm selection models in the scenario of predicting different algorithm performances. We show promising performance of the trajectory-based per-run algorithm selection with warm-starting.
  arXiv  Detail & Related papers  (2022-04-13T14:00:55Z)
• Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning [52.74071439183113]
  We study the predict-then-optimize framework in the context of sequential decision problems (formulated as MDPs) solved via reinforcement learning. Two significant computational challenges arise in applying decision-focused learning to MDPs.
  arXiv  Detail & Related papers  (2021-06-06T23:53:31Z)
• 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.