Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs
Vu Viet Hoang, Quoc Anh Hoang Nguyen, Hung The Tran · 2024
Read Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs by Vu Viet Hoang, Quoc Anh Hoang Nguyen, Hung The Tran (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15863.txt.
Introduction
Vu Viet Hoang and co-authors study a search problem in a 2024 paper on Bayesian optimization. The method hunts for the best setting of a costly black-box function. In real tasks, setting some variables costs money or effort. Past work knew each subset cost in advance and ignored total spend.
The team propose a method for cases where subset costs are random and unknown. One phase screens out weak subsets, and a later phase exploits the strong ones. They prove both quality loss and cost loss grow slower than linear over time. The result gives a firmer base for cheap, smart search under real cost limits.
Catalog record
| CREATOR | Vu Viet Hoang, Quoc Anh Hoang Nguyen, Hung The Tran |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15863
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs Vu Viet Hoang, Quoc Anh Hoang Nguyen, Hung The Tran Abstract Bayesian Optimization (BO) is a widely-used method for optimizing expensive-to-evaluate black-box functions. Traditional BO assumes that the learner has full control over all query variables without additional constraints. However, in many real-world scenarios, controlling certain query variables may incur costs. Therefore, the learner needs to balance the selection of informative subsets for targeted learning against leaving some variables to be randomly sampled to minimize costs. This problem is known as Bayesian Optimization with cost-varying variable subsets (BOCVS). While the goal of BOCVS is to identify the optimal solution with minimal cost, previous works have only guaranteed finding the optimal solution without considering the total costs incurred. Moreover, these works assume precise knowledge of the cost for each subset, which is often unrealistic. In this paper, we propose a novel algorithm for the extension of the BOCVS problem with random and unknown costs that separates the process into exploration and exploitation phases. The exploration phase will filter out low-quality variable subsets, while the exploitation phase will leverage high-quality ones. Furthermore, we theoretically demonstrate that our algorithm achieves a sub-linear rate in both quality regret and cost regret, addressing the objective of the BOCVS problem more effectively than previous analyses. Finally, we show that our proposed algorithm outperforms comparable baselines across a wide range of benchmarks. 1 FPT Software AI Center [email protected], [email protected] 2 Hanoi University of Science and Technology [email protected] Introduction Bayesian optimization (BO) is a powerful technique designed for the sample-efficient optimization of expensive-to-evaluate black-box objective functions. It has been effectively used in various important experimental design problems, such as hyperparameter optimization ( Snoek, Larochelle, and Adams 2012 ) , chemical synthesis ( Shields et al. 2021 ) , and particle accelerator control ( Kirschner et al. 2022 ) . Typically, BO has access to all query variables of the objective function, allowing it to re-evaluate any variable without additional hamper. However, in many practical situations, not all query variables can be easily modified. Some variables may follow specific distributions, and altering their values deterministically may incur costs. This setting is known as Bayesian Optimization with Cost-varying variable subsets (BOCVS), as introduced in ( Tay et al. 2023 ) . The aim is to identify optimal candidates for the objective function while minimizing incurred costs as much as possible. Naturally, greater control over the query variables leads to higher costs. Therefore, in each iteration, the learner must balance between the set of controllable query variables and the associated costs. We give an illustrative example with the BOCVS setting. Other concrete scenarios can be found in ( Tay et al. 2023 ) . In the context of adaptive control for manufacturing systems ( Kruger et al. 2011 ) , the goal is to optimize the production process to maximize output quality while managing the associated costs of process adjustments. The operator must adjust various control parameters, such as machine settings, temperature, and operational schedules, to enhance production quality. However, these adjustments can incur costs like energy consumption, maintenance or operating costs. To mitigate these costs, the operator can selectively modify certain control parameters while allowing others to vary randomly within a controlled range. The primary challenge lies in the fact that the cost constraints are not fully known or predictable, complicating the evaluation of the impact of randomized versus deterministic adjustments. These costs are often uncertain because they depend on fluctuating factors such as labor, or machine conditions. The operator must strike a balance between managing the risk of high, unknown costs and maintaining acceptable production quality. To the best of our knowledge, UCB-CVS ( Tay et al. 2023 ) is the first and only work that addresses this problem precisely. While UCB-CVS has shown promising theoretical and empirical results, there are some drawbacks. Firstly, the definition of their objective function focuses solely on finding the optimal solution and neglects the cost constraints. To incorporate cost constraints, the authors introduced the cost-varying cumulative regret, a cost-weighted version of the regular cumulative regret. While it can be proven that UCB-CVS achieves sublinear cost-varying cumulative regret, it is unclear whether it minimizes the total cost. For example, if there exists two control sets with similar performance while the cost is significantly difference, the sublinear rate for cost-varying regret stated in Theorem 4.1 ( Tay et al. 2023 ) does not emphasize the advantage of choosing cheaper control set. Therefore, we need a new definition of the objective function and regret to better reflect the goals of the BOCVS setting. Secondly, UCB-CVS assumes that the cost of every control set is deterministically known, which is a strict assumption that limits the algorithm’s practicality. It would be more desirable to have an algorithm that does not require precise knowledge of the cost of every control sets. Thirdly, UCB-CVS uses an \epsilon -schedule as a relaxation to enable exploration with cheaper control sets. However, choosing an appropriate \epsilon -schedule is challenging. In practice, UCB-CVS uses a simple explore-then-commit approach instead of an \epsilon -schedule. This creates a mismatch between the theoretical algorithm and its practical implementation. In this paper, we address an extension of the BOCVS problem where the cost of playing a subset is unknown. We introduce an efficient novel approach to analyzing the effectiveness of an algorithm by defining both quality regret and cost regret, which is a more rigorous analysis compared to previous work. An efficient algorithm should aim to minimize both types of regret. Consequently, we develop an algorithm designed to minimize these regrets simultaneously. The main contributions of this work are as follows: • We introduce an extension of the BOCVS problem in which the costs of the subset may be random and unknown. • We develop a cost-sensitive algorithm for the extension version. We derive an upper bound on the cumulative regret for our algorithm and theoretically show that the algorithm achieves sub-linear cumulative regret of both the objective function value and the cost. • We conducted an empirical evaluation of our proposed algorithm’s performance against baseline methods across a variety of experimental conditions. This included testing on both synthetic and real-world datasets, specifically a plant growth dataset and an airfoil self-noise dataset, which are relevant to the precision agriculture and advanced manufacturing applications discussed earlier. Preliminaries Gaussian Process and Bayesian Optimization We consider a query set \mathcal{X} and an objective function f:\mathcal{X}\rightarrow\mathbb{R} where \mathcal{X}\subset\mathbb{R}^{d} . The learner’s goal is to find the query that maximizes f , denoted as \mathbf{x}^{*}=\operatorname{argmax}_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x}) . However, f is a black-box function, meaning it is not available in a closed form and can only be evaluated by submitting a query \mathbf{x}_{t}\in\mathcal{X} at each iteration t , and receiving a noisy observation y_{t}=f\left(\mathbf{x}_{t}\right)+\xi_{t} , where each \xi_{t} is i.i.d. \sigma -sub-Gaussian noise with zero mean. Gaussian processes ( Williams and Rasmussen 2006 ) (GPs) are a popular choice as a surrogate model for optimizing f in BO because they enable exact posterior inference: The GP posterior estimate of f at any query \mathbf{x}\in\mathcal{X} after t iterations is a Gaussian with posterior mean and variance given by \displaystyle\mu_{t}(\mathbf{x}) \displaystyle:=\mathbf{k}_{t}(\mathbf{x})^{\top}\left(\mathbf{K}_{t}+\lambda\mathbf{I}\right)^{-1}\mathbf{y}_{t}, (1) \displaystyle\sigma_{t}^{2}(\mathbf{x}) \displaystyle:=k(\mathbf{x},\mathbf{x})-\mathbf{k}_{t}(\mathbf{x})^{\top}\left(\mathbf{K}_{t}+\lambda\mathbf{I}\right)^{-1}\mathbf{k}_{t}(\mathbf{x}) where \mathbf{y}_{t}:=\left(y_{j}\right)_{j=1}^{t}\in\mathbb{R}^{t},k is