samples, the posterior log likelihood would be $-n \overline{f}$, where $\overline{f}=\frac{1}{n} \sum_i f_i$ is in $\mathcal{F}_{smooth}$. The parameter $\lambda$ then corresponds naturally to the number of samples $n$.

This phenomenon of sampling being easier than optimization is primarily a “high temperature” or “low signal” phenomenon. As $\lambda$ approaches infinity, the distribution $\exp(-\lambda f)$ approaches a point mass at the minimizer of $f$. This connection goes back to at least [@KirkpatrickGV83] and one can easily derive a quantitative finite-$\lambda$ version of this statement for many function families. @MaCJFJ18 reconcile this with their separation by pointing out that their sampling algorithm becomes inefficient as $\lambda$ increases.

We first show a more elementary and stronger separation. We give a simple family of continuous Lipschitz functions which are efficiently samplable but hard even to approximately optimize. This improves on the separation in @MaCJFJ18 since our sampler is exact (modulo representation issues), and much simpler. The hardness of optimization here is in the oracle model, where the complexity is measured in terms of number of point evaluations of the function or its gradients.

While these oracle model separations rule out black-box optimization, they leave open the possibility of efficient algorithms that access the function in 