Budget-constrained Bayesian optimization
Lee, Eric Hans
Global optimization, which seeks to identify a maximal or minimal point over a domain Omega, is a ubiquitous and well-studied problem in applied mathematics, computer science, statistics, operations research, and many other fields. The resulting body of global optimization research is vast, ranging from heuristic and metaheuristic-driven approaches such as evolutionary search to application-driven systems such as multi-level, multi-fidelity optimization of physical simulations. Global optimization's inherent hardness underlies this sheer variety of different methods; absent any additional assumptions, obtaining an efficient certificate of global optimality is not possible. Consequently, there are no agreed-upon methods that exhibit robust, all-around performance like there are in local optimization. Data-driven algorithms and models, spurred by recent advances in cheap computing and flexible, open-source software, have been growing in popularity over recent years. Bayesian optimization (BO) is one such instance of this trend in global optimization. Using its past evaluations, BO builds a probabilistic model of the objective function to guide optimization, and selects the next iterate through an acquisition function, which scores each point in the optimization domain based on its potential to decrease the objective function. BO has been observed to converge faster than competing classes of global optimization algorithms.This sample efficiency is BO's key strength, and makes it ideal for optimizing objective functions that are expensive to evaluate and potentially contaminated with noise. Key BO applications that meet these criteria include optimizing machine learning hyperparameters, calibrating physical simulations, and designing engineering systems. BO's performance is heavily influenced by its acquisition function, which must effectively balance exploration and exploitation to converge quickly. Default acquisition functions such as expected improvement are greedy in the sense that they ignore how the current iteration will affect future ones. Typically, the BO exploration-exploitation trade-off is expressed in the context of a one-step optimal process: for the next iteration, choose the point that balances information quantity and quality. However, if we possess a pre-specified iteration budget h, we might instead choose the point that balances information quantity and quality over the next h steps. This non-myopic approach is aware of the remaining iterations and can balance the exploration-exploitation trade-off correspondingly. Non-myopic BO is the primary topic of this dissertation; we hope that making decisions according to a known iteration budget will improve upon the performance of classic BO, which is budget-agnostic.
Bayesian optimization; Gaussian process; Global optimization
Bindel, David S.
Birman, Ken; Frazier, Peter
Ph. D., Computer Science
Doctor of Philosophy
Attribution 4.0 International
dissertation or thesis
Except where otherwise noted, this item's license is described as Attribution 4.0 International