of continuous, differentiable functions for which approximate sampling can be done efficiently, but where approximate optimization requires exponential time (in an oracle model [*à la*]{} @NemiroskiY). In this work, we study the relationship of these two problems in more detail.

To aid the discussion, it will be convenient to consider a more general sampling problem where we want to sample with probability proportional to $\exp(-\lambda f(\vx))$ for a parameter $\lambda>0$. Such a scaling has no effect on the optimization problem, up to scaling of $\eps$. However changing $\lambda$ can signifcantly change the distribution for the sampling problem. In statistical physics literature, this parameter is the inverse temperature. For families ${\ensuremath{\mathcal{F}}}$ that are invariant to multiplication by a positive scalar (such as the family of convex functions), this $\lambda$ parameter has no impact on the complexity of sampling from the family. We will however be looking at families of functions that are controlled in some way (e.g. bounded, Lipschitz, or Smooth) and do not enjoy such an invariance to scale. E.g. in some Bayesian settings, each sample may give us a $1$-smooth negative log likelihood function, so we may want to consider the family $\mathcal{F}_{smooth}$ of $1$-smooth functions. Given $n$ i.i.d. 