  We propose a novel Bayesian approach to solve stochastic optimization
problems that involve finding extrema of noisy, nonlinear functions. Previous
work has focused on representing possible functions explicitly, which leads to
a two-step procedure of first, doing inference over the function space and
second, finding the extrema of these functions. Here we skip the representation
step and directly model the distribution over extrema. To this end, we devise a
non-parametric conjugate prior based on a kernel regressor. The resulting
posterior distribution directly captures the uncertainty over the maximum of
the unknown function. We illustrate the effectiveness of our model by
optimizing a noisy, high-dimensional, non-convex objective function.
