  Parallel surrogate optimization algorithms have proven to be efficient
methods for solving expensive noisy optimization problems. In this work we
develop a new parallel surrogate optimization algorithm (ProSRS), using a novel
tree-based "zoom strategy" to improve the efficiency of the algorithm. We prove
that if ProSRS is run for sufficiently long, with probability converging to one
there will be at least one point among all the evaluations that will be
arbitrarily close to the global minimum. We compare our algorithm to several
state-of-the-art Bayesian optimization algorithms on a suite of standard
benchmark functions and two real machine learning hyperparameter-tuning
problems. We find that our algorithm not only achieves significantly faster
optimization convergence, but is also 1-4 orders of magnitude cheaper in
computational cost.
