A Nonmyopic Approach to Cost-Constrained Bayesian Optimization
- URL: http://arxiv.org/abs/2106.06079v1
- Date: Thu, 10 Jun 2021 22:44:37 GMT
- Title: A Nonmyopic Approach to Cost-Constrained Bayesian Optimization
- Authors: Eric Hans Lee, David Eriksson, Valerio Perrone, Matthias Seeger
- Abstract summary: We formulate cost-constrained BO as a constrained Markov decision process (CMDP)
We develop an efficient rollout approximation to the optimal CMDP policy that takes both the cost and future iterations into account.
- Score: 10.078368988372247
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bayesian optimization (BO) is a popular method for optimizing
expensive-to-evaluate black-box functions. BO budgets are typically given in
iterations, which implicitly assumes each evaluation has the same cost. In
fact, in many BO applications, evaluation costs vary significantly in different
regions of the search space. In hyperparameter optimization, the time spent on
neural network training increases with layer size; in clinical trials, the
monetary cost of drug compounds vary; and in optimal control, control actions
have differing complexities. Cost-constrained BO measures convergence with
alternative cost metrics such as time, money, or energy, for which the sample
efficiency of standard BO methods is ill-suited. For cost-constrained BO, cost
efficiency is far more important than sample efficiency. In this paper, we
formulate cost-constrained BO as a constrained Markov decision process (CMDP),
and develop an efficient rollout approximation to the optimal CMDP policy that
takes both the cost and future iterations into account. We validate our method
on a collection of hyperparameter optimization problems as well as a sensor set
selection application.
Related papers
- Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index [57.045952766988925]
We develop a previously-unexplored connection between cost-aware Bayesian optimization and the Pandora's Box problem, a decision problem from economics.
Our work constitutes a first step towards integrating techniques from Gittins index theory into Bayesian optimization.
arXiv Detail & Related papers (2024-06-28T17:20:13Z) - Cost-Sensitive Multi-Fidelity Bayesian Optimization with Transfer of Learning Curve Extrapolation [55.75188191403343]
We introduce utility, which is a function predefined by each user and describes the trade-off between cost and performance of BO.
We validate our algorithm on various LC datasets and found it outperform all the previous multi-fidelity BO and transfer-BO baselines we consider.
arXiv Detail & Related papers (2024-05-28T07:38:39Z) - Poisson Process for Bayesian Optimization [126.51200593377739]
We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO)
Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
arXiv Detail & Related papers (2024-02-05T02:54:50Z) - Movement Penalized Bayesian Optimization with Application to Wind Energy
Systems [84.7485307269572]
Contextual Bayesian optimization (CBO) is a powerful framework for sequential decision-making given side information.
In this setting, the learner receives context (e.g., weather conditions) at each round, and has to choose an action (e.g., turbine parameters)
Standard algorithms assume no cost for switching their decisions at every round, but in many practical applications, there is a cost associated with such changes, which should be minimized.
arXiv Detail & Related papers (2022-10-14T20:19:32Z) - Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs [28.254408148839644]
We propose a non-myopic acquisition function that generalizes classical expected improvement to the setting of heterogeneous evaluation costs.
Our acquisition function outperforms existing methods in a variety of synthetic and real problems.
arXiv Detail & Related papers (2021-11-12T02:18:26Z) - Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions [74.00030431081751]
We formalize the notion of user-specific cost functions and introduce a new method for identifying actionable recourses for users.
Our method satisfies up to 25.89 percentage points more users compared to strong baseline methods.
arXiv Detail & Related papers (2021-11-01T19:49:35Z) - Cost-Efficient Online Hyperparameter Optimization [94.60924644778558]
We propose an online HPO algorithm that reaches human expert-level performance within a single run of the experiment.
Our proposed online HPO algorithm reaches human expert-level performance within a single run of the experiment, while incurring only modest computational overhead compared to regular training.
arXiv Detail & Related papers (2021-01-17T04:55:30Z) - Pareto-efficient Acquisition Functions for Cost-Aware Bayesian
Optimization [5.459427541271035]
We show how to make cost-aware Bayesian optimization for black-box functions.
On 144 real-world black-box function optimization problems, our solution brings up to 50% speed-ups.
We also revisit the common choice of Gaussian process cost models, showing that simple, low-variance cost models predict training times effectively.
arXiv Detail & Related papers (2020-11-23T15:06:07Z) - Frugal Optimization for Cost-related Hyperparameters [43.599155206275306]
We develop a new cost-frugal HPO solution for machine learning algorithms.
We prove a convergence rate of $O(fracsqrtdsqrtK)$ and an $O(depsilon-2)$-approximation guarantee on the total cost.
We provide strong empirical results in comparison with state-of-the-art HPO methods on large AutoML benchmarks.
arXiv Detail & Related papers (2020-05-04T15:40:44Z) - Cost-aware Bayesian Optimization [6.75013674088437]
Cost-aware BO measures convergence with alternative cost metrics such as time, energy, or money.
We introduce Cost Apportioned BO (CArBO), which attempts to minimize an objective function in as little cost as possible.
arXiv Detail & Related papers (2020-03-22T14:51:04Z)
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.