  Maximizing high-dimensional, non-convex functions through noisy observations
is a notoriously hard problem, but one that arises in many applications. In
this paper, we tackle this challenge by modeling the unknown function as a
sample from a high-dimensional Gaussian process (GP) distribution. Assuming
that the unknown function only depends on few relevant variables, we show that
it is possible to perform joint variable selection and GP optimization. We
provide strong performance guarantees for our algorithm, bounding the sample
complexity of variable selection, and as well as providing cumulative regret
bounds. We further provide empirical evidence on the effectiveness of our
algorithm on several benchmark optimization problems.
