  We consider the problem of optimizing a grey-box objective function, i.e.,
nested function composed of both black-box and white-box functions. A general
formulation for such grey-box problems is given, which covers the existing
grey-box optimization formulations as special cases. We then design an
optimism-driven algorithm to solve it. Under certain regularity assumptions,
our algorithm achieves similar regret bound as that for the standard black-box
Bayesian optimization algorithm, up to a constant multiplicative term depending
on the Lipschitz constants of the functions considered. We further extend our
method to the constrained case and discuss special cases. For the commonly used
kernel functions, the regret bounds allow us to derive a convergence rate to
the optimal solution. Experimental results show that our grey-box optimization
method empirically improves the speed of finding the global optimal solution
significantly, as compared to the standard black-box optimization algorithm.
