Optimization for Heterogeneous Evaluation Costs

This direction is merged into another direction: uniform cost assumption (heterogeneous evaluation costs), cost-prioritized initialization. Its last version stays readable and citable here.

Version 1 of 170 papers74 conceptsfrozen 2026-10-04

Most optimization algorithms—from Bayesian Optimization (BO) to Stochastic Gradient Descent (SGD)—operate on a hidden assumption: every sample costs the same. Whether you are evaluating a set of hyperparameters, testing a chemical compound, or probing a sensor, the "budget" is typically measured in the number of iterations.

However, in the real world, costs are rarely uniform. As Jasper Snoek, Hugo Larochelle, and Ryan P Adams pointed out in Practical Bayesian Optimization of Machine Learning Algorithms, training a neural network for 100 epochs takes significantly longer than training it for 10. If an algorithm treats these two evaluations as equal, it will waste vast amounts of time on expensive, low-utility configurations.

The research direction of Cost-Aware Optimization seeks to replace the "unit cost" assumption with a framework that prioritizes information gain per unit of resource (time, money, or energy) expended.

The Information-per-Dollar Intuition

The core mechanism of cost-aware optimization is a modification of the "acquisition function." In standard BO, an acquisition function like Expected Improvement (EI) tells the algorithm where to sample next based on potential reward. Cost-aware variants, such as those explored by Majid Abdolshah and colleagues in Cost-aware Multi-objective Bayesian optimisation, essentially divide this improvement by the expected cost.

By optimizing for the ratio of $\frac{\text{Expected Improvement}}{\text{Expected Cost}}$, the algorithm naturally develops a "frugal" strategy. It begins by exploring "cheap" regions of the search space to build a rough map of the objective function. Only when the potential gains from expensive regions outweigh their high costs does the algorithm "invest" its budget there. Chi Wang and Qingyun Wu demonstrated in Frugal Optimization for Cost-related Hyperparameters that this cautious, cost-first approach can find optimal configurations up to three orders of magnitude faster than traditional methods.

Multi-Fidelity and the Power of Proxies

A major facet of this research involves Multi-Fidelity Optimization. In many engineering tasks, you have access to multiple ways to evaluate a design: a fast but "noisy" simulation (low fidelity) and a slow but "precise" physical experiment (high fidelity).

Kirthevasan Kandasamy and co-authors introduced MF-GP-UCB in Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations, which uses low-fidelity queries to "filter" the search space. The intuition is simple: don't spend a thousand dollars on a high-fidelity test for a configuration that a one-dollar simulation already shows is mediocre. This hierarchical approach is particularly effective in materials science, where Sk Md Ahnaf Akif Alvi and Brent Vela use Deep Gaussian Processes to balance cheap density calculations against expensive melting point measurements in Deep Gaussian Process-based Cost-Aware Batch Bayesian Optimization for Complex Materials Design Campaigns.

Pathwise and Transition Costs

In some scenarios, the cost isn't just about the evaluation itself, but the movement between points. In robotics or chemical processing, changing parameters (like temperature or physical location) takes time and energy.

Standard BO "jumps" around the search space to find the global optimum. However, David Walz introduced SnAKe in SnAKe: Bayesian Optimization with Pathwise Exploration, which treats optimization as a path-finding problem. By solving a version of the Traveling Salesman Problem over the points it wants to sample, the algorithm minimizes transition costs, ensuring that the "route" to the optimum is as efficient as the samples themselves.

Knowing When to Quit

Cost-awareness also changes the "stopping problem." Traditional algorithms stop after a fixed number of steps. But if the next sample is extremely expensive and unlikely to yield a better result than what we already have, we should stop early.

Qian Xie and Ziv Scully address this in Cost-aware Stopping for Bayesian Optimization, providing a principled economic framework for deciding when the "price" of the next experiment exceeds its expected value. Similarly, Yi Ding and Alex Renda developed Cello (Cello: Efficient Computer Systems Optimization with Predictive Early Termination and Censored Regression), which uses censored regression to predict if a configuration is going to be "bad" and terminates the evaluation mid-way to save resources.

Why It Works: Resource Efficiency over Sample Efficiency

The shift from sample efficiency (minimizing the number of evaluations) to resource efficiency (minimizing total cost) is the defining characteristic of this field. By explicitly modeling the cost landscape—whether it is input-dependent latencies in cloud configurations (Burkhard Ringlein) or varying computational effort in SGD (Jianfeng Lu in HeteRSGD)—these methods align algorithmic search with the economic and physical realities of the problems they solve.

Papers in this version

Showing 60 of 70 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimization_for_heterogeneous_evaluatio_c02836a2,
  title = {Optimization for Heterogeneous Evaluation Costs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-for-heterogeneous-evaluation-costs/rdr_c02836a2dd734dae804969b00965bf3f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimization_for_heterogeneous_evaluatio_c02836a2_v1,
  title = {Optimization for Heterogeneous Evaluation Costs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-for-heterogeneous-evaluation-costs/rdr_c02836a2dd734dae804969b00965bf3f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}