  Applying Bayesian optimization in problems wherein the search space is
unknown is challenging. To address this problem, we propose a systematic volume
expansion strategy for the Bayesian optimization. We devise a strategy to
guarantee that in iterative expansions of the search space, our method can find
a point whose function value within epsilon of the objective function maximum.
Without the need to specify any parameters, our algorithm automatically
triggers a minimal expansion required iteratively. We derive analytic
expressions for when to trigger the expansion and by how much to expand. We
also provide theoretical analysis to show that our method achieves
epsilon-accuracy after a finite number of iterations. We demonstrate our method
on both benchmark test functions and machine learning hyper-parameter tuning
tasks and demonstrate that our method outperforms baselines.
