  Bayesian Optimization is a popular approach for optimizing expensive
black-box functions. Its key idea is to use a surrogate model to approximate
the objective and, importantly, quantify the associated uncertainty that allows
a sequential search of query points that balance exploitation-exploration.
Gaussian process (GP) has been a primary candidate for the surrogate model,
thanks to its Bayesian-principled uncertainty quantification power and modeling
flexibility. However, its challenges have also spurred an array of alternatives
whose convergence properties could be more opaque. Motivated by these, we study
in this paper an axiomatic framework that elicits the minimal requirements to
guarantee black-box optimization convergence that could apply beyond GP-based
methods. Moreover, we leverage the design freedom in our framework, which we
call Pseudo-Bayesian Optimization, to construct empirically superior
algorithms. In particular, we show how using simple local regression, and a
suitable "randomized prior" construction to quantify uncertainty, not only
guarantees convergence but also consistently outperforms state-of-the-art
benchmarks in examples ranging from high-dimensional synthetic experiments to
realistic hyperparameter tuning and robotic applications.
